プロジェクトオイラー2. ~ Even Fibonacci numbers ~

No.2 Even Fibonacci numbers

Q. 直前の2項の和を次の項として生成されるフィボナッチ数列において, 1, 2, から始めたときの最初の10項は次のようになる.

\begin{align*}
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots
\end{align*}

この数列の4,000,000未満の項で偶数のものの総和はいくらか.

ループを用いて 4,000,000 未満の項を順に生成し, 偶数であるもののみを足し上げていきます.

a = 1
b = 2
c = a + b
Sum = 2
while c <= 4000000:
    if c % 2 == 0:
        Sum += c
    a = b
    b = c
    c = a + b
print(Sum)

この数列を見ると,

1 (奇数), 2(偶数), 3(奇数), 5(奇数), 8(偶数), 13(奇数), …

と 2個おきに偶数項がでてきます.

もとの数列を $\{F_n\}$ として， $a_n=F_{3n-1}, b_n=F_{3n}$ とおきます.

$\{a_n\}$ が偶数項のみ取り出した数列になります.

すると,

$\begin{align*} a_{n+1} &= F_{3n+2}\\ &= F_{3n+1}+F_{3n}\\ &= F_{3n-1}+2F_{3n}\\ &= a_n+2b_n \end{align*}$

また,

$\begin{align*} b_{n+1} &= F_{3n+3}\\ &= F_{3n+2} + F_{3n+1}\\ &= F_{3n+2} + F_{3n} + F_{3n-1}\\ &= a_{n+1} + b_n+a_{n-1} \end{align*}$

これを解いて $\{a_n\}$ の漸化式を求めると,

$\begin{align*} a_{n+2} = 4a_{n+1} + a_n \end{align*}$

となるので, これをもとに $\{a_n\}$ の項を順に求めて足していくと,

a = 2
b = 8
c = a + 4 * b
Sum = a + b
while c <= 4000000:
    Sum += c
    a = b
    b = c
    c = a + 4 * b
print(Sum)