プロジェクトオイラー 問１０４

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１０４「両端がパンデジタルなフィボナッチ数」
フィボナッチ数列は再帰的な関係によって定義される:

F_n = F_n-1 + F_n-2
F₅₄₁ (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. 
そして, F₂₇₄₉ (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

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






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。
<pre class="brush:python;collapse:true" title="問１０４">
def f(s):
pl, ps = len(s), sorted(s)
a, b, c, d, k, g, n = 1, 0, 1, 0, 1, 0, pl*2
while sorted(str(a)[:pl])!=ps or sorted(str(c)[-pl:])!=ps:
a, b, c, d, k, m = a+b, a, c+d, c, k+1, len(str(a))-n
if pl<m:
u, v = 10**m, 10**n
a, b, c, d, g = a//u, b//u, c%v, d%v, g+m
g += len(str(a))
return k, g

P = "123456789"
k, t = f(P)
print "k    :", k
print "digit:", t
</pre>

問題のまま実装すると、数千桁から数万桁の数値の加算に処理時間がかかり、とても１分では終わりません。
フィボナッチ数の先頭と末尾それぞれの必要な桁数分だけ桁調整して計算します。
なお、桁調整の際に必要な桁を超える桁数は累積しておき、後で全体桁数を把握できるようにします。

１．関数f(s)
・文字列sに含まれる文字が先頭と末尾に順不同で存在するフィボナッチ数での項番と桁数を返します。
・変数plは文字列sの文字列長、変数psは文字列sを1文字ずつ昇順に並べた要素として持つリストです。
・kはフィボナッチ数の項番、
　aはフィボナッチ数F_kの上から必要な桁数分、bはフィボナッチ数F_k-1の上から必要な桁数分、
　cはフィボナッチ数F_kの下から必要な桁数分、dはフィボナッチ数F_n-1の下から必要な桁数分、
　gはフィボナッチ数Fkの桁数です。
・変数nは本問の計算に必要な桁数です。
　大きな値にすると加算処理に時間がかかるので必要な桁数以上でなるべく小さな値とします。
　題意にあう必要なチェックをするために少なくとも引数sの文字数分は必要で、また加算の繰り上がりの影響を吸収するためにさらに引数sの文字数分を考慮しておきます。合わせて、計算に必要な桁数nは、引数sの2倍の値とします。

・whileループ内でのフィボナッチ数計算の継続チェックは以下の通りです。
　先頭と末尾を引数と同じ桁数だけ取り出して昇順に並べて、事前に用意した変数psと比較し、どちらかが不一致ならば処理を継続します。

・whileループ内ではフィボナッチ数の計算をします。
　フィボナッチ数F_k、F_k-1の先頭部分a,bにそれぞれa+b、aを設定します。
　フィボナッチ数F_k、F_k-1の末尾部分c,dにそれぞれc+d、cを設定します。
　項番kを１つ進めます。
　変数mは先頭部分から桁調整で減らす桁数で、フィボナッチ数の先頭部分の計算結果の桁数と計算に必要な桁数nの差です。

・変数mはすぐに正の値になりますが、あまり頻繁に桁調整しなくても処理速度に影響ないので、mがplより大きい場合、先頭と末尾両方の桁調整を行います。
　変数uは先頭部分の末尾から減らす桁数分の10の累乗値で、フィボナッチ数F_k、F_k-1それぞれの先頭部分a,bをuで割った商を新たにa,bとします。
　変数vは末尾部分の先頭から減らす桁数分の10の累乗値で、フィボナッチ数F_k、F_k-1それぞれの末尾部分c,dをvで割った余りを新たにc,dとします。
　桁数gには調整して減らした桁数mを累積していきます。

・フィボナッチ数の計算が終わりwhileループ終了後に、桁数gにはフィボナッチ数の先頭部分aの桁数を足して、全体桁数にしておきます。
　なお、計算中に桁調整をしていなければ変数aはフィボナッチ数そのものです。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
k    : 329468
digit: 68855