問題
五角数は 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 の最小値を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
回答
第2n項までの5角数の数列を作成してから、第n項の5角数と第1項～第n項の5角数の和及び差がいずれも5角数か否かを判定した。
append属性等の参照に時間がかかるということであったので、あらかじめappend属性、add属性を変数に入れておいた。また、要素が所定の集合に含まれるか否かについては、setオブジェクトを参照することにより、速度向上を目指した。
結果として、最初に和と差が5角数となるような数は見つかったものの、それが最小であることは確かめることができなかった。
def pe44():
start, stop = 1, 10**8
pen = ((n * ( 3*n - 1))//2 for n in xrange(start, stop))
p_list, p_set = [], set([])
ans = 10**10
i = 0
append = p_list.append
add = p_set.add
while 1:
append(pen.next())
append(pen.next())
add(p_list[2*i])
add(p_list[2*i+1])
d = search(p_list[i],p_list[:i+1],p_set)
if d:
min_d = min(d)
if min_d < ans:
found_answer(min_d)
ans = min_d
if ans < p_list[i+1] - p_list[i]:
break
i+=1
return ans
def found_answer(n):
print n
#@debug
def search(p1,p_list,p_set):
d = []
for p2 in p_list:
if (p1+p2 in p_set) and (p1-p2 in p_set):
#if (p1+p2 in p_list) and (p1-p2 in p_list):
d.append(p1-p2)
return d
pe44()