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

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

問７４「60個の循環しない項を持つ階乗列となる数を特定せよ」

145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す.
このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる.
例を見てみよう.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69から始めた場合, 列は5つの循環しない項を持つ.
また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

－－－－－


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

def h(n):
	c = 1
	for i in xrange(2, n+1): c *= i
	return c

def g(n, d): return sum([d[s] for s in str(n)])

def f(n, m):
	d = {}
	for i in xrange(10): d[str(i)] = h(i)
	N = []
	for i in xrange(n):
		s, M = i, []
		while (s not in M) and (i<=s):
			M.append(s)
			s = g(s, d)
		t = len(M)
		if s<i: t += N[s]
		N.append(t)
	return sum([1 for i in N if i==m])

n = 1000000
print f(n, 60)

１．関数h(n)
・nの階乗値を返します。再帰呼び出しは使わず単純ループで掛け算します。
・再帰呼び出しにした場合、n≧1000で「maximum recursion depth exceede」エラーになるので、再帰呼び出しの深さの限界値をsys.setrecursionlimit()で設定する必要があります。

２．関数g(n, g)
・数字nの各桁の階乗値の和を返します。
・dは1桁数字の階乗値を持つ辞書です。但し、キーは文字型です。
・数字nを文字型にして一文字ずつ階乗値辞書から階乗値を取得し、最後にsum関数で合計します。

３．関数f(n, m)
・n未満の数字のうち、循環しない各桁階乗和をmもつものの個数を返します。
・辞書dとして、関数gで使用する階乗値辞書を作っておきます。
・リストNには、i番目の要素に数字iの循環しない各桁階乗和の個数を入れます。
・ループ変数iはn未満の数を昇順に１つずつとります。
・sは各桁階乗和の計算対象の候補です。初期値はループ変数iです。
・リストMには、各桁階乗和を１つずつ進めながら循環部分になるまで持ちます。
・whileループで、計算対象候補sがすでにリストMにあれば循環部分突入なので終了です。
　また計算対象候補sがループ変数i未満なら、その先の循環部分までの個数はリストNにあるのでやはりループは終了です。
・tで各桁階乗和をためたリストMの個数を求め、さらに計算対象候補sがループ変数i未満だった場合はそれ以降の循環部分に達するまでの個数を足します。
・上記の状態のtが数字iでの、循環しない各桁階乗和の個数です。リストNに追加しておきます。

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