五角数の判定はこれのnが整数であること。
n=\frac{\sqrt{24N+1}+1}{6}
Problem 44 「五角数」
五角数は 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 の最小値を求めよ.
def hoge():
penta = []
n = 1
while True:
pk = n * (3 * n - 1) / 2
for pj in penta[::-1]: # 差が小さくなるものから順にチェック
if (((24 * (pk + pj) + 1) ** 0.5 + 1) / 6).is_integer() and \
(pk - pj) in penta:
return int(pk - pj)
penta.append(pk)
n += 1
print(hoge())
和と差の判定の順番を入れ替えると死ぬほど遅くなる。
チェック回数が倍率ドンとかそんな感じなんだろうと思うが一切確証はない。
xxx@xxx$ time python3 wa-sa.py
5482660
real 0m1.757s
user 0m1.752s
sys 0m0.004s
xxx@xxx$ time python3 sa-wa.py
5482660
real 1m39.104s
user 1m38.960s
sys 0m0.008s