PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 51 / 素数の桁置換

*3の第1桁を置き換えることで 13, 23, 43, 53, 73, 83という6つの素数が得られる。

56**3の第3桁と第4桁を同じ数で置き換えることを考えよう。この5桁の数は7つの素数をもつ最初の例である。
56003, 56113, 56333, 56443, 56663, 56773, 56993

56003はこのような性質を持つ最小の素数である。

いくつかの桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ。
注:連続した桁でなくてもよい。

Problem 51 - Project Euler

考察1:3桁以上の入れ替えが必要

この問題で考える素数は3の倍数ではないので,各桁の数字の和を3で割った余りは0ではありません。この条件を入れ替える桁と入れ替えない桁に分けて調べます。

入れ替える桁については

  • 余り0:00,33,66,99 の 4 通り
  • 余り1:22.55,88 の 3 通り
  • 余り2:11,44,77 の 3 通り

入れ替えない桁の数字の和を x とします。x を3で割った余りが0のとき,上の結果から素数は最大で 3+3=6 個できます。同様に x が余り1,2のときは7個できるので,2桁の入れ替えでは8個の素数は作れません。3桁以上の入れ替えが必要です。

また,次のこともわかります。

  • 一の位は入れ替えません。偶数が5個できて,これらは素数ではないからです。
  • 首位の数字を0で置き換えることはありません。問題文中の例で「*3→3」は考えていないことからわかります。

考察2:入れ替えは3桁か4桁か

入れ替える桁数が多いほど素数の形が限定されて条件が厳しくなるので,次の順番で調べることになります。

  1. 5桁のうち3桁を入れ替える
  2. 5桁のうち4桁を入れ替える
  3. 6桁のうち3桁を入れ替える
  4. 6桁のうち4桁を入れ替える
  5. ……

このうち「5桁のうち4桁を入れ替える」は簡単に否定できます。「一の位は入れ替えない」ルールにより,入れ替えは首位4桁でしか起こりません。素数は奇数であることも考えると,y=1,3,5,7,9 について
1111y, 2222y, 3333y, 44444y, 5555y,
6666y, 7777y, 8888y, 9999y,
が素数かどうか調べれば十分です。条件をみたす数はありませんでした。

計算

以上をもとにコードを書いたところ,得られた答えは「120386」。不正解でした。どうやら素数の列に自分自身が含まれないといけないらしいです。

The Project Euler in C# Open Source Project on Open Hub : Individual Commit Page

というわけで,答えが出たら逆算して n を求めるようなコードを書いてやっと正解しました。