読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 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 の最小値を求めよ。

Problem 44 - Project Euler

答えを1つ求める

ある数 a が五角数かどうかは,Pn=a が整数解 n をもつかどうかで判定できます。この2次方程式の解を IntegerQ にわたせばOK。

 n=\dfrac{1+\sqrt{1+24a}}{6}

適当に範囲をきめて,Pi ± Pj が五角数になる i, j (i< j) を探すと
{1020, 2167}
がみつかります。

1分を超えてしまいました。また,この方法で最小性を示すのは現実的ではありません。ずっと先に差が小さい2数があるかもしれず,この可能性を否定するには P[n] の階差が P[2167]-P[1020] になる範囲まで調べないといけないからです。1分ではとても無理です。

検索範囲を狭くする

Pi, Pj が条件をみたすとき,
Pj - Pi = Pa, Pj + Pi = Pb
をみたす a, b が存在します。添字の大小は i< a< j< b。上式は
Pj = Pi + Pa, Pb = 2Pi + Pa
と書き換えられるので,(i, j) ではなく (i, a) に注目して
Pi + Pa, 2Pi + Pa
が五角数になる条件を求める方が検索範囲が狭くて得です。

また,D = Pa なので Pa の最小値を求めれば最小条件もみたせます。

計算してみましょう。まず 1≦i≦1100, i+1≦a≦2000 で探すと
{1020, 1912}
がみつかるので,1≦i≦1911, i+1≦a≦1912 で探せばOKです。無事1分におさまりました。