Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

现在我们来一起探讨欧拉计划中的第二道题。老规矩，如果你想在欧拉计划官方网站上看到这道题请点击 阅读原文 。

它的大致意思是：斐波那契数列的每一项都等于前两项的加和，设斐波那契的前两项为1和2，则它的前十项为：1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 请试求出不大于四百万的斐波那契数列中所有偶数项的和。

如果使用编程的方法的话，这道题并不是什么难题，你完全可以遍历不大于四百万的斐波那契数列。不过如果凭借人脑和手工计算的话，四百万可不是一个小数量级。我们不得不采取一种手段，来让它变得简单。

因为它只涉及斐波那契的偶数项，我们自然会想到把偶数项分离出来。当米开朗基罗对“大卫”的制作创作过程有这样一句名言：“你只需要用锤子把不像‘大卫’的地方敲掉就好了。”这里我们也可以借鉴这句话，只需要把斐波那契数列中的奇数项敲掉就好了。

如果你仔细关系就会发现斐波那契数列奇偶数的排列规律。

奇、偶、奇、奇、偶、奇、奇、偶、奇、奇、偶、奇、奇、偶、奇、奇……

你并不需要为这样的事情感到新奇，因为有：

奇数+偶数=奇数
奇数+奇数=偶数
偶数+偶数=偶数

笔者现在可以用非常简单的方法来向你证明它，因为奇数可以表示为某一个偶数加一，当然这里说的偶数是包括零的。那么偶数可以表示为某一个整数乘以二。那么偶数+偶数就可以写成某一个整数n乘以二加另一个整数m乘以二，则有：

这样一来n+m肯定是一个整数，它作为一个整体乘以二就满足了偶数可以表示为某一个整数乘以二。所以偶数+偶数=偶数是成立的。既然偶数+偶数=偶数是成立的，那么则有：奇数+偶数=偶数+偶数+1=偶数+1=奇数；同时就有：奇数+奇数=偶数+偶数+1+1=偶数+2=偶数+偶数=偶数。

那么现在我们就写出斐波那契数列的偶数项：

2，8，34，144，610，2584，10946，46368，196418，832040，3524578……

笔者一下子就写出来了不大于四百万的所有偶数项，你八成会觉得笔者是不是开挂了。实际上如果你一个一个的算，直到算到第一个大于四百万的项停止的话，你得到的数列里面也只有三十三项，这并不是什么巨大的计算量。

不过现在笔者要告诉你的是如何快速的找到这十一个偶数项。如果你记得斐波那契数列那个大兔子生小兔子的故事，你就应该知道1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 并不是唯一的写法。当然这里笔者懒得给你讲那个老兔子生大兔子，大兔子生小兔子，小兔子生小小兔子的冗长故事。所以我们就使用另一种方法来讲解如何得到斐波那契数列的偶数项。

如果说斐波那契数列的第一项是1，第二项是2的话，那么它的第零项是什么呢？我们知道它的每一项都等于前两项的加和，那么这样一来第二项的2就应该等于第一项的1加上第零项。那么第零项就是1。相似的我们还可以推知它的第负一项是零……

接下来，我们想要知道的是它偶数项之间的规律。加入我们看它的偶数项,奇数项用a和序数的方式表示：

……,0,[a0],[a1],2,[a3],[a4],8,[a6],[a7],34,[a9],[a10],144,[a12],[a13]……

那么第五项的8，是由a3+a4得到的。a4又是由a2+a3得到的，a3又是由a2+a1得到的。就有：

通过推导我们得知，在斐波那契数列中的每一个偶数项都等于，它前一个偶数项的四倍加上它前两个偶数项。这样一来，快速写出它不大于四百万的偶数项就不是什么巨大的工程了。当然，如果我们把这个数量级进一步扩大那么则需要找到更多的规律来简化我们的计算。目前来说，如果想要手工处理巨大数量级的数据的一个思路就是找到这些数据之间的关系和规律，从而简化计算。如果你喜欢笔者的文章，你可以关注笔者的微信公众号：yevgeny_liu

本文转载自异步社区

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF912A1000013D94B1B0ADC052C0