[Project Euler]Problem 2

Problem 2:

　　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.

问题2：

　　求斐波那契数列中不超过四百万的偶数的和。

方法一:

　　直接按题意写代码

def f1(limit):
    Fib=[1,2]
    while Fib[-2]+Fib[-1]<limit:
        Fib.append(Fib[-2]+Fib[-1])
    return sum(filter(lambda x:x%2==0,Fib))

方法二:

观察可知斐波那契数列 中的奇偶性为 奇偶奇、奇偶奇、奇偶奇,以3为周期循环:

　　证明 A1=1,A2=2,An=An-1+An-2 ,A3n+2(n为整数)为偶数其他A3n+1,A3n+3(n为整数)为奇数.
　　A1=1,A2=2,A3=A1+A2=3
　　可知 A3n+2(n为整数)为偶数其他A3n+1,A3n+3(n为整数)为奇数 在n=0时成立.
　　当A3n+2(n为整数)为偶数其他A3n+1,A3n+3(n为整数)为奇数 在n时成立
　　则 A3(n+1)+1=A3n+3+A3n+2=奇数+偶数=奇数.
　　A3(n+1)+2=A3n+4+A3n+3=奇数+奇数=偶数
　　A3(n+1)+3=A3n+5+A3n+4=偶数+奇数=奇数
　　数学归纳法可知 A1=1,A2=2,An=An-1+An-2 ,A3n+2(n为整数)为偶数其他A3n+1,A3n+3(n为整数)为奇数.

因此题目转化为求 斐波那契数列 中 小于四百万的3n+2项的和

　　An+3=An+2+An+1=(An+1+An)+An+1=2An+1+An 
　　An+6=2An+4+An+3=2(2An+2+An+1)+2An+1+An=4An+2+4An+1+An=4An+3+An 
　　A3(n+2)+2=4A3(n+1)+2+A3n+2 
　　令Bn=A3n+2 
则B0=2,B1=8,Bn=4*Bn-1+Bn-2 

def f2(limit):
    B=[2,8]
    while B[-2]+4*B[-1]<limit:
        B.append(B[-2]+4*B[-1])
    return sum(B)