プロジェクトオイラー2.

この記事の所要時間: 235

No.2 Even Fibonacci numbers

問題.

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

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

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

考え方とプログラム例(Python)

1. 4,000,000 未満の項すべてを調べる

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

計算時間は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{eqnarray*} a_{n+1} &=& F_{3n+2}\\ &=& F_{3n+1}+F_{3n}\\ &=& F_{3n-1}+2F_{3n}\\ &=& a_n+2b_n \end{eqnarray*}

また,

\begin{eqnarray*} 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{eqnarray*}

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

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

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

計算時間は 3.02\times 10^{-4} 秒でした.

答えはこの下の行にあります. 反転してください.

A. 4613732

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加