Project Euler - Probrem 34

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　　 ProjectEuler.net（英語サイト）

Problem 34

145は面白い数である.1! + 4! + 5! = 1 + 24 + 120 = 145となる.
各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.
注: 1! = 1 と 2! = 2 は総和に含めてはならない.

－－－－－


私の解答例は以下です。畳んでいます。

def h(n):
	if n<=1: return 1
	else: return h(n-1)*n

def g():
	i, m = 0, h(9)
	while True:
		i += 1
		if m*i<10**(i): break
	return m*i

def f():
	d = dict([[i, h(i)] for i in xrange(10)])
	return [i for i in xrange(3, g()) if i==sum([d[int(t)] for t in str(i)])]

L = f()
print sum(L),L

３つの関数を使っています。

１．関数h(n)
・nの階乗を返します。詳しくはproblem20を参照してください。

２．関数g()
・各桁の階乗値の和が元の数と一致するような数を求めるにあたり、その最大可能値、つまり候補として検討すればいい最大値を返します。

・値が小さい場合は各桁の階乗値の方が元の数よりも大きいことがありますが、桁数を増やしていくと、9をn乗して桁数分足した値が、その桁数の最小値（10のn乗）にすら達しない桁数が来ます。
　そのような桁数までチェックすれば十分ということになります。

・具体的には、その桁の最大値として9がn個並んだ数字を想定し、9の階乗値を桁数分足した値が、その桁数の最小値（10のn乗）を下回った場合に、9の階乗値を桁数分足した値を返します。

３．関数f()
・各桁の数の階乗の和が自分自身と一致するような数のリストを返します。
・d = dict([[i, h(i)] for i in xrange(10)])
　階乗値の辞書です。0から9の整数とこれに対応する階乗値をあらかじめ用意しておきます。

・return [i for i in xrange(3, g()) if i==sum([d[int(t)] for t in str(i)])]
　内包表記で書いています。
　まずfor文で、問題に合うように1と2は飛ばして3から最大可能値までの整数をループ変数iとします。
　その後、後ろのif文でiと各桁の階乗値の和が同じ場合だけforの前に渡します。
　そしてfor文の前で渡されたiをリストにためます。
　なお、sum関数により以下で説明する内包表記のリストの合計値を求めています。
　まずfor文でiを文字型にした値から1文字ずつループ変数tとします。
　そしてforの前に渡し、int型に戻して階乗値辞書を検索し対応する階乗値を取得しリストにためます。
　
４．関数の外
・関数f()で問題に合う値のリストが戻ってくるので、sum関数でその合計を計算します。

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