Problem 104 「両端がパンデジタルなフィボナッチ数」 †

フィボナッチ数列は再帰的な関係によって定義される:

Fn = Fn−1 + Fn−2
F541 (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. そして, F2749 (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

Fkが, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき, kを求めよ.


解法
足し算を繰り返すとある桁以下は上位9桁に影響を与えなくなってきます。
上位17桁くらいとっておけばまず安全に上位9桁を正確に算出できます。
安全マージンを取って上位20桁以下は切り捨て。
として計算しました。
C++などでは16桁くらいで計算するとよいでしょう
下位9桁はModをとればよいだけです。


num_cut(FL3,FL2,FL3,FL2):-FL3 <10^20,!.
num_cut(FL3,FL2,FL33,FL22):-!,FL33 is FL3//10,FL22 is FL2//10.

check(List):-!,
	sort(List,[49,50,51,52,53,54,55,56,57]).


calc(K,_,FL2,_,FR2):-
	number_codes(FL2,ListL),
	FR22 is FR2 mod 10^9,
	number_codes(FR22,ListR),
	[X1,X2,X3,X4,X5,X6,X7,X8,X9|_]=ListL,
	check([X1,X2,X3,X4,X5,X6,X7,X8,X9]),
	check(ListR),
	!,
	write(K).
calc(K,FL1,FL2,FR1,FR2):-
	FL3 is (FL1+FL2),
	num_cut(FL3,FL2,FL33,FL22),
	FR3 is (FR1+FR2) mod 10^9,
	K1 is K+1,
	!,
	calc(K1,FL22,FL33,FR2,FR3).

main104:-
	calc(2,1,1,1,1).

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年03月07日 08:39