Project Euler Problem 044

http://projecteuler.net/index.php?section=problems&id=44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044

五角数は 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 の最小値を求めよ.

五角数を求める関数の逆関数を作ってGreedyに調べた。いまいち。

import math
import itertools
import datetime


def pentagonal(n):
    return n * (3 * n - 1) / 2


def is_pentagonal(n):
    x = (math.sqrt(24 * n + 1) + 1) / 6.0
    return x == int(x)


def euler044():
    result = 0
    
    cache = [ 0 ]
    for i in itertools.count(1):
        c = pentagonal(i)
        cache.append(c)
        if i < 3: continue
        for j in xrange(i - 1, -1, -1):
        
            b = cache[j]
            a = c - b
            
            if not (a < b < c): break
            
            if is_pentagonal(a) and is_pentagonal(b-a):
                result = b-a
                print (a, b, c), result
                return




begin = datetime.datetime.now()
euler044()
end = datetime.datetime.now()
print end - begin

答え: 5482660 (1560090, 7042750, 8602840)
実行時間: 1.119102秒くらい