PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 061 / 巡回図形数

三角数,四角数,五角数,六角数,七角数,八角数は多角数であり,それぞれ以下の式で生成される。

三角数P3,n=n(n+1)/21, 3, 6, 10, 15, ...
四角数P4,n=n21, 4, 9, 16, 25, ...
五角数P5,n=n(3n-1)/21, 5, 12, 22, 35, ...
六角数P6,n=n(2n-1)1, 6, 15, 28, 45, ...
七角数P7,n=n(5n-3)/21, 7, 18, 34, 55, ...
八角数P8,n=n(3n-2)1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ。

  • この集合は巡回的である。最後の数も含めて各数の後半2桁は次の数の前半2桁と一致する
  • それぞれ多角数である:三角数 (P[3,127]=8128), 四角数 (P[4,91]=8281), 五角数 (P[5,44]=2882) がそれぞれ別の数字で集合に含まれている

4桁の数の組で上の2つの性質をもつはこの組だけである。
三角数,四角数,五角数,六角数,七角数,八角数がすべて表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ。

Problem 61 - Project Euler


三角数~八角数があらわれる順番をどう処理すればいいのかわからず,今までずっと解けないでいましたが,他の問題で Permutations を使ったのを機にやっと解けました。4~8の順列の頭に3を加えたものを使います。

Prepend[#, 3] & /@ Permutations[{4, 5, 6, 7, 8}]

「後半2桁は次の数の前半2桁と一致する」はグラフ理論で処理します。この条件をみたす数 i, j に対して i->j を集めたグラフを作って,長さ6のサイクルを探しました。

ちなみに条件をみたすサイクルは

1281 → 8128 → 2882 → 8256 → 5625 → 2512 → 1281

です。順に3, 4, 7, 8, 6, 5, 3角数です。

この問題が解けたことで問題番号が素数の問題を50問解いたことになり,Prime Obsession というアワードをもらいました。

f:id:variee:20170611194503p:plain