「プロジェクトオイラー問２５」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問２５」(2014/02/14 (金) 04:18:00) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://projecteuler.net/problem=25



*Problem 25 「1000桁のフィボナッチ数」 †
フィボナッチ数列は以下の漸化式で定義される:

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桁になる最初の項の番号を答えよ.





解法
フィナボッチ数列の近似式と対数計算から求めます。
式から求めるのは少しめんどくさいですね。

 fina(N,Result):-
 	Result is N*log((1+5^0.5)/2)/log(10)-log(5^0.5)/log(10).
 
 main25:-
 	between(1,5000,N),
 	fina(N,Result),
 	999=<Result,
 	!,
 	write([N,Result]).