プロジェクトオイラー Problem30

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 30
驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

• 1634 = 14 + 64 + 34 + 44
• 8208 = 84 + 24 + 04 + 84
• 9474 = 94 + 44 + 74 + 44

ただし, 1=14は含まないものとする.
この数たちの和は 1634 + 8208 + 9474 = 19316 である.
各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.


私の解答例は以下です。

def g(n):
	i, m = 0, 9**n
	while True:
		i += 1
		if m*i<10**i: break
	return m*i
	
def f(n):
	L = []
	for i in xrange(2, g(n)):
		if i==sum([int(t)**n for t in str(i)]): L.append(i)
	return L
	
L = f(5)
print sum(L),L

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

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

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

・i, m = 0, 9**n
　初期値設定で、桁数iに0、mに9のn乗値を設定します。

・while True:
 i += 1
　9をn乗して桁数分足した値が、その桁数の最小値（10のn乗）にすら達しない桁数が来るまで、無限ループで桁数iを1ずつ増やします。

・　if m*i<10**i: break
　return m*i
　9をn乗して桁数分足した値が、その桁数の最小値（10のn乗）にすら達しない桁数かを判定し、このような桁数に達したら、桁数iのループを終了し、9をn乗して桁数分足した値を返します。
　

２．関数f(n)
・for i in xrange(2, g(n)):
　ループ変数iは、2以上で検討に十分な値（関数g(n)の戻り値）までの整数です。

・if i==sum([int(t)**n for t in str(i)]): L.append(i)
　各桁をn乗した数の和が元の数と一致するような数をリストLに貯めていきます。

・return L
　問題にある数を貯めたリストLを返します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
443839 [4150, 4151, 54748, 92727, 93084, 194979]