Project Euler Problem 045
http://projecteuler.net/index.php?section=problems&id=45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される. 三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ... 五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ... 六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ... T285 = P165 = H143 = 40755であることが分かる. 次の三角数かつ五角数かつ六角数な数を求めよ.
40755以上の六角数を調べて、五角数かつ三角数であればよい。
Problem 042とおなじ要領で逆関数を作って判定した。
こまかいことだけど、五角数 and 三角数 と調べずに、三角数 and 五角数 と調べると少し遅くなる。成立しにくい条件から判定すること。
import math import itertools import datetime def triangle(n): return n * (n + 1) / 2 def pentagonal(n): return n * (3 * n - 1) / 2 def hexagonal(n): return n * (2 * n - 1) def is_triangle(n): x = (math.sqrt(1 + 8 * n) - 1) / 2.0 return int(x) == x def is_pentagonal(n): x = (math.sqrt(1 + 24 * n) + 1) / 6.0 return int(x) == x def is_hexagonal(n): x = (math.sqrt(1 + 8 * n) + 1) / 4.0 return int(x) == x def euler045(): T = triangle P = pentagonal H = hexagonal isT = is_triangle isP = is_pentagonal isH = is_hexagonal for i in itertools.count(144): val = H(i) if isP(val) and isT(val): print val break begin = datetime.datetime.now() euler045() end = datetime.datetime.now() print end - begin
答え: 1533776805 (= T55385 = P31977 = H27693)
実行時間: 0.049960秒くらい