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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 60 / 素数ペア集合

素数3, 7, 109, 673は非凡な性質を持っている。任意の2つの素数を任意の順でつなげると,また素数になっている。たとえば7と109を用いると,7109と1097の両方が素数である。これら4つの素数の和は792である。これはこのような性質をもつ4つの素数の集合の和の中で最小である。

任意の2つの素数をつなげたときに別の素数が生成される5つの素数の集合の和の中で最小のものを求めよ。

Problem 60 - Project Euler

解を1つ求める

ブルートフォースを覚悟していたのですが,グラフ理論を使ったら意外にすんなり解けました。

  • Prime[i] と Prime[j] からできる数が両方とも素数となるような点 i, j を辺で結んでグラフを作る
  • 5個の点からなるクリーク(フルメッシュな部分グラフ)を探す
  • その頂点に対応する素数の和を求める

ちなみに FindClique の結果は
{6, 692, 751, 868, 1051}
で,素数に直すと
{13, 5197, 5701, 6733, 8389}
です。

最小性の検証

ここまでやったところで本家サイトに答えを入力し,正解となったのですが,よく考えて見ると最小性を示していません。5個目の素数は大きいが和は小さい組があるかもしれないからです。以下,これを検証します。

すでに和として 26033 を得ているので,nmax の上限はわかります。2861です。

解は3組ありました。

{6, 692, 751, 868, 1051}
{91, 160, 317, 2787, 2240}
{4, 203, 347, 1481, 2111}

これらに対応する値の最小値を求めて完全終了です。