問題
三角数, 五角数, 六角数は以下のように生成される.
三角数 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であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
回答方針
六角数の各項は三角数の奇数項なのだけど、このような事実は無視して、とりあえず簡単にすべての項が等しくなるような仕組みを考えてみた。
1. 各角数のジェネレータgeneと値valueとを一組にしてリストang_list化する。
2. 各値valueが等しくなるまで、値の最大値ang_maxよりも小さい値valueをジェネレータで更新する。valueを更新したときは、flagをFalseにする。
3. 各角数の全てで値valueの更新がなければ、各角数の値valueが最大値ang_maxと等しい、つまり、全ての角数の値が等しいということなので、終了する。
コード
from mytools import *
def t(n):
return n*(n+1)/2
def p(n):
return n*(3*n-1)/2
def h(n):
return n*(2*n-1)
@get_time
@main_start
def main():
#(TRI_START,PEN_START,HEX_START) = (2, 2, 2)
(TRI_START,PEN_START,HEX_START) = (286, 166, 144)
MAX = 10**8
tri_gene = ( t(n) for n in xrange(TRI_START, MAX))
pen_gene = ( p(n) for n in xrange(PEN_START, MAX))
hex_gene = ( h(n) for n in xrange(HEX_START, MAX))
ang_list = [
{'value': tri_gene.next(), 'gene': tri_gene},
{'value': pen_gene.next(), 'gene': pen_gene},
{'value': hex_gene.next(), 'gene': hex_gene}
]
ang_max = max(ang_list[0]['value'], ang_list[1]['value'], ang_list[2]['value'])
flag = False
while not flag:
flag = True
for ang in ang_list:
if ang['value'] < ang_max:
ang['value'] = ang['gene'].next()
flag = False
if ang['value'] > ang_max:
ang_max = ang['value']
print ang_max
main()