不超过400万的偶斐波那契数之和

Question

我用的方法虽然能解决问题，但我觉得效率不高，因为一旦我输入一个太大的数字，它就不行了。

def fib_even(n):
    fib_even = []
    a, b = 0, 1
    for i in range(0,n):
        c = a+b
        if c%2 == 0:
            fib_even.append(c)
            a, b = b, a+b
return fib_even

def sum_fib_even(n):
    fib_evens = fib_even(n)
    s = 0
    for i in fib_evens:
        s = s+i
    return s

n = 4000000
answer = sum_fib_even(n)
print answer

比如说，输入4000000就不行，但输入400就可以。有没有更有效的方法呢？

Answer 1

其实不需要把所有的斐波那契数都存起来，可能这样存储会导致性能问题。

Answer 2

并不需要计算所有的斐波那契数。

注意：接下来我会使用更标准的初始值 F[0]=0 和 F[1]=1 来表示斐波那契数列。Project Euler #2 是从 F[2]=1, F[3]=2, F[4]=3 开始的……对于这个问题，两种选择得到的结果是一样的。

所有斐波那契数的求和（热身练习）

递归方程

F[n+1] = F[n] + F[n-1]

也可以理解为

F[n-1] = F[n+1] - F[n]

或者

F[n] = F[n+2] - F[n+1]

将这个从 1 到 N 的求和（记得 F[0]=0, F[1]=1）放在左边是斐波那契数的和，右边是一个望远镜求和，里面的项都相互抵消了。

sum(n=1 to N) F[n] = (F[3]-F[2]) + (F[4]-F[3]) + (F[5]-F[4])
                     + ... + (F[N+2]-F[N+1])
                   = F[N+2] - F[2] 

所以对于问题中提到的 N=4,000,000 的求和，只需要计算

F[4,000,002] - 1

使用一些超快速的方法来计算单个斐波那契数。可以用对半分和平方的方法，这相当于对迭代矩阵的指数运算，或者使用基于黄金比例的指数公式（以必要的精度计算）。

因为大约每 20 个斐波那契数就会多出 4 位数字，最终结果将大约有 800000 位数字。最好使用一种可以容纳所有这些数字的数据类型。

---

偶数斐波那契数的求和

只要查看前 10 或 20 个斐波那契数，就会发现所有偶数的下标都是 3*k。通过减去两个连续的递归可以验证这一点，得到

F[n+3]=2*F[n+2]-F[n]

所以 F[n+3] 总是和 F[n] 有相同的奇偶性。进一步计算可以找到一个关于相隔三个下标的成员的递归关系，如下所示

F[n+3] = 4*F[n] + F[n-3]

设置

S = sum(k=1 to K) F[3*k]

并对 n=3*k 的递归求和得到

F[3*K+3]+S-F[3] = 4*S + (-F[3*K]+S+F[0])

或者

4*S = (F[3*K]+F[3*K]) - (F[3]+F[0]) = 2*F[3*K+2]-2*F[2]

所以所需的和的公式是

S = (F[3*K+2]-1)/2

用黄金比例公式快速计算一下，可以得出 N 应该是多少，以便 F[N] 刚好在边界之下，因此 K=N 除以 3 应该是多少，

N = Floor(  log( sqrt(5)*Max )/log( 0.5*(1+sqrt(5)) )  )

---

将欧拉问题简化为一个简单的公式

在原始问题中，可以发现 N=33，因此和是

S = (F[35]-1)/2;

---

问题的简化及其后果

考虑到问题中错误表述的情况，N=4,000,000，因此 K=1,333,333，和是

(F[1,333,335]-1)/2

这个和仍然大约有 533,400 位数字。没错，大整数类型可以处理这样的数字，只是计算时需要一些时间。

如果以每行 60 个数字、80 行的格式打印，这个数字会占用 112 页纸，仅仅是为了让你了解输出的样子。