※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。




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]).