のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 45

三角数、五角数、六角数に共通して現れる最小の数は40755である。次に共通する数を求める。

 多角数についてはコチラ([ウィキペディア:多角数])。

 まず、全てに共通する数をHとする。これは六角数でもあるはずなので、HexagonalのHを取った。これが、ある三角数Tiであり、またある五角数Pjでもあるので、

2H = 2Ti = i(i+1)
2H = 2Pj = j(3j-1)
そして元の六角数に対しても
2H = 2Hk = (2k-1) * 2k

という関係になっている。ここで気付くのが、三角数も六角数も連続する2数の積の形をしていることである。つまり六角数列を構成する数は、必ず三角数列に含まれる。そしてそれらは連続する2数の積であり、さらに六角数の定義から、その2数は(奇数)☓(次の偶数)となる。

 ここまで分かれば、あとは簡単である。五角数(便宜上そう言ったが、正確には五角数の2倍)の中から、(奇数)☓(次の偶数)の形をしたものを見つけ出せば良い。隣り合う数の積かどうかは、ルートを取ればだいたい分かる。

 コードとしては全然美しくないが、答えは一瞬で出てしまう。

プログラミング関係ない…☆