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秒くらい