プロジェクト オイラー Pb.25

プロジェクトオイラーというものがあります。


本家は海外のサイトですが、数学の頭の体操的な問題が
200問超掲載されています。
これをプログラムで解くのがなかなか面白いのですが、
ブログのネタに困ったときはこの問題を1つずつ解いてみることにします。


というわけで早速Problem 25を解いてみます。
私はPythonをこよなく愛する人間ですので、
問題は常にPythonで解いてみることにします。

Problem 25.
フィボナッチ数列は以下の漸化式で定義される:
Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.

最初の12項は以下である.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

12番目の項, F12が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

答えがどのくらいの規模になるのかまず考えてみます。


フィボナッチ数を F(n) と表すことにします。
m桁の自然数で最小のものは 10**(m-1) ですので、

F(k) = 10**(m-1)
F(k+1) = 10**(m-1) 

という(ありえないですが)F(k)とF(k+1)がm桁で最小であった場合を考えれば

F(k+2) = 2 * 10**(m-1)
F(k+3) = 3 * 10**(m-1)
F(k+4) = 5 * 10**(m-1)
F(k+5) = 8 * 10**(m-1)
F(k+6) = 13 * 10**(m-1)

となり、少なくともF(k+6)までに桁が繰り上がることがわかります。
つまり、F(k)とF(k+6)を比較したら、必ず桁数が異なるということです。


すると、F(n)が1000桁に達するようなnは、n <= 6000であることがわかります。
この程度の規模であれば力技プログラムでも解けますね。


というわけで解答はこんな感じでしょうか。

import time
_START = time.time()

n = 1
a, b = 1, 1
while len(str(a)) != 1000:
    a, b = b, a + b
    n += 1
print n

print '計算時間 %.3f [sec]' % (time.time() - _START)

計算時間は私の環境で 1.656 [sec] でした。