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

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

問８０「平方根の10進展開」
よく知られているように、自然数の平方根が整数ではないならば、それは無理数である。
そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。
2の平方根は1.41421356237309504880..., であり、その頭から100桁の数字を合計すると475になる。

初めの100個の自然数の平方根のうち、無理数について、それぞれの頭から100桁の数字を足した数の総和を求めよ。



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






私の回答例は以下の通りです。

def f(n, m):
	L, c = [i*i for i in xrange(n+1)], 0
	for i in xrange(n+1):
		if i in L: continue
		M, s, t = [], 0, i
		for j in xrange(m):
			N = [s*10+k for k in xrange(10)]
			for k in range(10)[::-1]:
				w = s*10+k
				if w*k<=t: break
			M.append(k)
			s, t = w+k, (t-w*k)*100
		c += sum(M)
	return c

n, m = 100, 100
print f(n, m)

平方根を開平法で求めます。

（参考）
・開平法（wikipedia）

・ルートを開こう（中村文則氏のサイト）


１．関数f(n, m)
・n個の自然数の平方根のうち、無理数について、それぞれの頭からm桁分の数字の和の総和を返します。

・リストLは自然数の２乗のリストで、その要素は平方根が有理数になる自然数す。

・変数cに求める総和を累積していきます。初期値は0です。

・ループ変数iが平方根を求める対象の自然数です。
　iがリストLに含まれている場合は対象外なので処理を飛ばします。

・リストMは平方根の各桁ごとの数字をためていくリストです。
・sは初期値0です。
・端数tは、元の数から、平方根を求めた桁までの２乗を差し引いた端数です。
　最初は平方根は1桁も求まっていないので、tの初期値はiです。

・ループ変数jは平方根の左端の桁位置を0とした桁位置を示します。

・for k in range(10)[::-1]:
w = s*10+k
if w*k<=t: break
　ループ変数kは、0から9までの配列を逆順に1つずつ取り出します。
　1つ前のループで計算したsの桁を1つ上げて（10倍して）kをたした値をwとし、
　wとkの積がtを超えない最大値となるkを探します。
　このkが平方根の求める桁の値です。

・s, t = w+k, (t-w*k)*100
　上記のkで1桁進みましたので次の桁の準備をします。
　wとkの和をsとします。
　新たに決定した桁の分である、wとkの積を端数tから差し引きます。
　100の平方根が10なので、平方根は元の数2桁ごとに1桁決まります。
　このため端数tは100倍しておきます。


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