読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 104 / 両端がパンデジタル

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

Fn = Fn−1 + Fn−2

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

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

Problem 104 - Project Euler


上9桁,下9桁を取り出すとか,それを{1, 2, ..., 9} と比較するとかは簡単なんですが,結果が出るまでに13分かかりました。大きなフィボナッチ数を扱うのはやはり大変みたいで,Range を調節してなんとか現実的な計算時間におさめました。


「下9桁の条件をクリアしたものだけ上9桁を調べる」で速くなります。こちらは3分ほど。ついでに下9桁の判定を Mod に変えてみましたが,こちらは変化なし。


桁数も調べてみました。68855桁……


追記(2017/04/20)

PCを新調して Parallelize で並列化したら1分におさまりました。