プロジェクトオイラー Problem23

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

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

Problem 23
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである.
たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい,
真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1+2+3+4+6=16となるので, 最小の過剰数である.
よって2つの過剰数の和で書ける最少の数は24である.
数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている.
2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.


私の解答例は以下です。
－－－－－

def g(n):
	L = []
	for i in xrange(1, n):
		if n%i: continue
		elif n<i*i: break
		L.append(i)
		if 1<i<n/i: L.append(n/i)
	return sum(L)
	
def f(n):
	L0 = [i for i in xrange(n+1) if i<g(i)]
	L1 = [i+j for i in L0 for j in L0 if i+j<=n]
	L2 = set(L1)
	return (n*(n+1)/2)-sum(L2)
	
print f(28123)

－－－－－

２つの関数を使用しています。

１．g(n)
・「真の約数」の和を返します。
・problem 21　の関数d(n)を再利用しました。

２．f(n)
・リストL0は、n以下の過剰数のリストです。
　for文で0～nの値を順番にループ変数iに設定し、後ろのif文へ渡します。
　i<g(i)で、自分自身よりも「真の約数の和」の方が大きい（過剰数）の場合、for文の前に渡してその計算値（この場合はiそのまま）をリストに設定していきます。

・リストL1は、リストL0の任意の２つの和のうち、n以下の値のリストです。
　最初のfor文でリストL0から値を順に取り出してループ変数iに設定し、
　次のfor文でもリストL0から値を順に取り出してループ変数jに設定します。
　これでL0から重複ありで2つ取り出した状態です。
　これで後ろのif文に値を渡します。
　if i+j<=n で、取り出したiとjの和がn以下ならば、for文の前の計算式（ここでは、i+j）に値を渡してその計算値をリストに設定していきます。

・リストL2は、リストL1内の値の重複を削除し、ユニークにします。
　set関数で引数のリストを、値のユニークなタプル（要素を変更できない配列）に変換します。

・return (n*(n+1)/2)-sum(L2)
　(n*(n+1)/2)は、1～nまでの和の公式そのままです。
　ここから、n以下の２つの過剰数の和を引くことで、
　２つの過剰数の和で書き表せない正の整数の和が返却されます。
　
　　
３．関数の外
・上記の関数fに、28123を渡せば求める数値になります。


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

（追記）
・20120715
　ソースコード部分にSyntaxHighlighterを導入。