2014年8月20日水曜日

プロジェクトオイラー 問95

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

問95「友愛鎖」
ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ.
面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる.

さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす.
12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)
この鎖は出発点に戻っているため, 友愛鎖と呼ばれる.

いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ.






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






私の回答例は以下の通りです。
def d(n):
	c, m = 1, int(n**.5)
	for i in xrange(2, m+1):
		if not n%i:
<			c += i
<			j = n//i
<			if i<j: c += j
	return c

def f(n):
	L, N = [d(i) for i in xrange(n+1)], []
	for i in xrange(n+1):
		j, M = L[i], []
		while (j not in M) and (j<=n):
<			M.append(j)
<			j = L[j]
		if M and i==M[-1] and len(N)<len(M): N = [i]+M[:-1]
	return len(N), min(N), N

n = 1000000
n,m,L = f(n)
print "min:",m
print "num:",n
print "chain:",L


1.関数d(n)
・関数d(n)はnの友愛数を返します。問21を改良しました。
・数値nの「真の約数」の上限は、その定義からnの正の平方根です。
 n**(0.5) が、0.5乗ということで、nの正の平方根です。
・変数cに真の約数を累積していきます。
 //演算は割り算の商(整数)で、%演算は割り算の余りです。
 変数iのforループで、nがiで割り切れるとき、変数cにiを累積します。
 割り切れるときは余り0で、%演算の結果がFalseになるので、not演算子でこのような場合を捉えます。
 またこのときの商j=n//iも約数なので、i<jならこれも変数cに累計します。
 nが平方数でiがその平方根の場合、i=jなのでiだけ累積しjは累積しません。

2.関数f(n)
・関数f(n)は、n以下の友愛数リストを取得し、その友愛数をたどり、最長の友愛鎖を返します。
・リストLは、その位置のオフセット値の友愛数を持つリストです。例)L[220]=284
・リストNには、最長の友愛鎖を格納します。
・ループ変数iは、友愛鎖をたどる最初の数値です。
・変数jは次の友愛数が格納されます。
・リストMには、数値iから始まる友愛鎖を格納します。
・while文のループ条件は、
 友愛数jが友愛鎖リストMになく、上限値以下であることとしています。
・友愛鎖リストMを最長友愛鎖リストNに保存する条件は、
 リストMに値があり、友愛鎖たどりの最初の数値iが友愛鎖の最後の値と一致し、
 リストNよりも長い(最長の友愛鎖)こととしています。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
min: 14316
num: 28
chain: [19116, 31704, 47616, 83328, 177792, 295488, 629072, 589786, 294896, 358336, 418904, 366556, 274924, 275444, 243760, 376736, 381028, 285778, 152990, 122410, 97946, 48976, 45946, 22976, 22744, 19916, 17716, 14316]

0 件のコメント:

コメントを投稿