PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 45 / 三角数,五角数,六角数

三角数,五角数,六角数は次のような数である。

三角数Tn=n(n+1)/21, 3, 6, 10, 15, ...
五角数Pn=n(3n-1)/21, 5, 12, 22, 35, ...
六角数Hn=n(2n-1)1, 6, 15, 28, 45, ...

T285 = P165 = H143 = 40755である。

次の三角数かつ五角数かつ六角数な数を求めよ。

Problem 45 - Project Euler

多角数 PolygonalNumber[r, n] のリストを作って,Intersection でその共通部分を求めます。

三角数,五角数,六角数はすべて2次式で,2次の係数は 1/2,3/2,2。六角数は三角数の約4倍の値をとります。40755で一致した後はかなり先までいかないと同じ値になりません。調べてみたら55100個先でした。

55100はトライアル&エラーで見つけました。10^3でダメ→10^4でダメ→10^5で成功→5*10^4でダメ→……とやってるうちに見つかります。

FC版ドラクエ4で838861枚バグを自力でみつけたときのことを思い出しました。

5章のカジノで、【コイン】を838861枚買おうとすると,本来ならば1枚20ゴールドなので16,777,220Gもかかってしまうはずが,何とたったの4ゴールドで買えてしまう。

5章開始早々に【はぐれメタルのたて】を手に入れたり,【ほしふるうでわ】を人数分揃えたり、【いのりのゆびわ】をいくらでも集められたりと,もはやお得っていうレベルじゃないやりたい放題の裏技。
ドラゴンクエスト大辞典を作ろうぜ!!第三版 Wiki

普通にループをまわして探すなら,nを1ずつ増やすんじゃなく1000ずつとか 2^k ずつとか増やしていって,Intersection の Min を求めるといいと思います。

追記(2017/04/18)

読み返してみたら我ながらひどい解法というか,実質的には全然解けてないのでもう一度やります。

いま見るとこの問題はペル型方程式の問題ですね。まず三角数と六角数が一致する条件を求めてみました。

この結果式はちょっと見にくいかもしれませんが,要するに
x=2k+1, z=k+2
です。次は三角数と五角数について調べます。

これまた見にくいと思うので,TeXで書いておきます。

 y_k=\dfrac{1}{6}\left\{1+\dfrac{1}{2}(\sqrt{3}-1)(7+4\sqrt{3})^{2k+1}-\dfrac{1}{2}(\sqrt{3}+1)(7-4\sqrt{3})^{2k+1}\right\}

y2 に対する五角数 g[y2] が答えです。

おまけとして y_k の最初の10個も調べました。ペル型方程式の解だけあってすごい勢いで増えます。