Project Euler - Probrem 44

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

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

Problem 44
五角数は Pn = n(3n-1)/2で生成される. 最初の10項は
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
である.
P4 + P7 = 22 + 70 = 92 = P8である. しかし差 70 - 22 = 48は五角数ではない.

五角数のペア PjとPkについて, 差と和が五角数になるものを考える.
差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ.

－－－－－


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

def g(n):
	import math
	return not (1+math.sqrt(1+n*24))%6

def f():
	i, t, L, M = 0, 0, [], []
	while len(M)<1:
		i += 1
		s = i*(3*i-1)//2
		for j in L[::-1]:
			if g(s+j) and g(s-j):
				M.append((j, s))
		L.append(s)
	return M

t = f()[0]
print t[1]-t[0], t

上記プログラムでは、求めた差がその時点での五角数の数列の増分よりも大きいので、これよりも大きな値のところで、最小値となる差が存在する可能性があります。
増分の方が差よりも大きくなるところまで検証したいところですが、１分ルールを満たせず、五角数の和と差が五角数である最小の組を見つけたところで処理を終了しています。
結果として答えは合っていましたが、さらに改良が必要です。

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

１．関数g(n)
・五角数の判定です。

・return not (1+math.sqrt(1+n*24))%6
　定義式から、x(3x-1)/2 = nを満たす整数xが存在すればnは五角数です。
　xの二次方程式として、二次方程式の解の公式より、
　x = (1±√(1+24n))/6
　このxが整数かどうかは、＋か－のどちらで判定しても同じなので、ここでは＋の方を採用しています。

２．関数f(n)
・問題の条件に合う値をリストLにためていきます。

・while len(M)<1:
　Mに1でも解がたまれば終了にします。
　上限値を設けて全ての値を検証したいのですが、1分ルールを守れませんでしたので、ここでは1つ見つけたら終了しています。

・i += 1
　iは1ずつ増えるカウンターです。

・s = i*(3*i-1)//2
　sはi番目の五角数です。

・for j in L[::-1]:
　差が小さいものを抽出するため、すでにチェックの済んだ大きい値から順に比較します。
　リストLには五角数が小さい順に入っていますので、逆順にループして大きい値から取り出して、ループ変数jとします。
　リスト[開始位置:終了位置:刻み]です。[::-1]で逆順に1つずつです。

・if g(s+j) and g(s-j):
　　M.append((j, s))
　sとjの和と差が両方とも五角数の場合、s,jの組をリストMにためていきます。

・L.append(s)
　sをチェック済みの五角数としてリストLにためていきます。

３．関数の外
・t = f()[0]
　print t[1]-t[0], t
　関数fの戻り値から、その差を求めます。


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