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未満の項で偶数のものの総和はいくらか.
考え方とプログラム例(Python)
1. 4,000,000 未満の項すべてを調べる
ループを用いて 4,000,000 未満の項を順に生成し, 偶数であるもののみを足し上げていきます.
1 2 3 4 5 6 7 8 9 10 11 |
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 |
計算時間は\(5.18\times 10^{-4}\)秒でした.
2. 偶数項のみの数列を考える
この数列を見ると,
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\}\) の項を順に求めて足していくと,
1 2 3 4 5 6 7 8 9 10 |
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 |
計算時間は \(3.02\times 10^{-4}\) 秒でした.