PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 128 / 六角形タイルの差分

六角形のタイルを図のように反時計回りに置いていく。

f:id:variee:20180602222929g:plain

タイル n とそれに隣接するタイルのうち,書いてある数字と n の差が素数となるタイルの枚数を PD(n) と定義する。

たとえばタイル8の場合,まわりのタイルの数字と8の差は 12, 29, 11, 6, 1, 13 となるので PD(8) = 3 であり,同様に PD(17) = 2 である。

PD(n) の最大値は3であることが示せる。
PD(n) = 3 をみたす n を昇順に並べた数列の10番目の項は271である。

この数列について2000番目のタイルを求めよ。

本家:Problem 128 - Project Euler
日本語訳:Problem 128 - PukiWiki

実験

与えられた図をもとに調べると最初の6項は 1, 2, 8, 19, 20, 37 で,まわりの数や差は次のようになっています。カッコで囲んだ数は素数です。

n まわりの数 差(ソート後)
1 2,3,4,5,6,7 1,(2),(3),4,(5),6 1,(2),(3),4,(5),6
2 1,3,7,8,9,19 1,1,(5),6,(7),(17) 1,1,(5),6,(7),(17)
8 2,9,19,20,21,37 6,1,(11),12,(13),(29) 1,6,(11),12,(13),(29)
19 2,7,8,18,36,37 (17),12,(11),1,(17),18 1,(11),12,(17),(17),18
20 8,21,37,38,39,61 12,1,(17),18,(19),(41) 1,12,(17),18,(19),(41)
37 8,19,20,36,60,61 (29),18,(19),1,(23),24 1,18,(19),(23),24,(29)

規則性があるのかないのかはっきりしない感じですが,中央のマスの数字をxとして,まわりに x+1 や x-1 があったり,連続する2数(または3数)があったりすることがわかります。

以下,8~19や20~37のような並びを「周期」と呼ぶことにし,n 個目の周期の先端を H(n),末端を T(n) であらわします。8~19について考えます。

まわりのタイルのパターンは4つ

中央のマスの数字をxとして,そのまわりの6枚のタイルに書かれた数字のパターンを分類してみました。

辺の途中

9, 11, 13, 15, 17, 19は
{x-1, x+1, y, y+1, z, z+1} 型です。

  • x-(x-1)=1, (x+1)-x=1 は素数ではない
  • x-y, x-(y+1) のうち素数はたかだか1個
  • z-x, (z+1)-x のうち素数はたかだか1個

素数はたかだか1+1=2個しかありません。

先端,末端以外の頂点

10, 12, 14, 16, 18は
{x-1, x+1, y, z-1, z, z+1} 型です。
x-1, x+1が素数を与えないことは上で見たので,他の数について考えます。

たとえばx=10のときy=3, z=23です。H(1)=2, H(2)=8, H(3)=20から順に1,2,3進んだところにy=3, x=10, z=23があり,一般に
{z-H(n+1)} - {x-H(n)} と {x-H(n)}-{y-H(n-1)} は一致します。H(n)はつねに6の倍数なので,次のことが言えます。

  • y, zの偶奇は等しい
  • zとz+1, z-1の偶奇は異なる

要するに偶奇に注目するとxのまわりの残り4数は {y, z}, {z+1, z-1} の2グループに分類できるので,素数はたかだか2個しかありません。

先端

H(n) =3n(n-1)+2 の真上から反時計回りに
H(n+1), H(n+1)+1, H(n)+1, H(n-1), T(n), T(n+1)
が並びます。H(n), T(n) を6で割った余りが0, 5であることを考えると,素数を与える可能性があるのは次の3箇所です。
H(n+1)+1, T(n), T(n+1)

末端

T(n) の真上から反時計回りに
T(n+1), H(n), H(n-1), T(n-1), T(n)-1, T(n+1)-1
が並びます。先端の場合と同様,素数を与える可能性があるのは3箇所です。
H(n), H(n-1), T(n+1)-1

解法

先端と末端について調べればOK。0.5秒でした。

tail[n] - head[n]などを展開した式(すべて1次式)を使うと0.3秒に縮まりますが,この差は誤差の範囲内ですね。