PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 111 / 重複桁を持つ素数

重複した桁を含む 4 桁の素数を考える。
各桁に1は最大3個含まれ,このような素数は9つある。

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111


n 桁の素数を考える。各桁に d が最大 M(n, d) 個含まれるとする。このような素数が N(n, d) 個あり,それらの和が S(n, d) であるとする。


Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

S(4, d) (0 <= d <= 9) の総和は 273700 である。
S(10, d) の総和を求めよ。

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

n=4の場合

4桁の素数のうち,1を3個含むものは9個あります。これは

 \{1,1,1,x\}\quad (x=0,\, 1,\, \cdots,\, 9)

の permutation が素数になるかどうか調べればわかります。

0を2個含むものが13個あることは {0, 0, x, y} の permutation について調べればわかります。

n=10の場合

以上を一般化すればn=10の場合も解けます。ただ,桁数が増える分,調べる回数も増えます。本当は

「ある数を9個含むものがあるかどうか調べる」
→「なければ8個含むものを調べる」
→「なければ7個含むものを調べる」
→……

のようにして解くべきなのですが,面倒だったので8個までで十分なことを事前に調べた上で答えを出しました。


内訳はこうなっていました。

d M(10,d) N(10,d) S(10,d)
0 8 8 38000000042
1 9 11 12882626601
2 8 39 97447914665
3 9 7 23234122821
4 9 1 4444444447
5 9 1 5555555557
6 9 1 6666666661
7 9 9 59950904793
8 8 32 285769942206
9 9 8 78455389922

n=4 の場合もそうですが,M(n, d)=n-1, n-2 まで考えれば十分なのが不思議です。