Project Euler 問題37で切り捨て可能な素数を求めました。今回は、木構造を使って、すべての右切り捨て可能な素数を求めてみました。
切り捨て可能素数の定義と例
それ自身が素数である自然数 $n$ から、右の桁を何桁削除しても、その数が素数であるような場合、$n$ を右切り捨て可能素数（right-truncatable prime）と呼ぶ。
それ自身が素数である自然数 $n$ から、左の桁を何桁削除しても、その数が素数であり、それぞれの桁が 0 でない場合、$n$ を左切り捨て可能素数（left-truncatable prime）と呼ぶ。
左切り捨て可能素数に、0 を含む数を含めると、1060+7（素数）のようにいくらでも大きな桁の左切り捨て可能な素数が存在することになります。このような場合を排除するため、0 を含む数を左切り捨て可能素数から除いています。
Wikipedia と Prime Glossary（左および右）の記事を参考にしました。
739397 の右の桁を削除して得る
73939、7393、739、73、7
はすべて素数になるため、右切り捨て可能素数である。
また、739397 の左の桁を削除して得る
39397、9397、397、97、7
はすべて素数になるため、左切り捨て可能素数である。
739397 は、どちらの定義も満たす最大の素数である。
すべての右切り捨て可能素数を求める
右切り捨て可能素数は、以下の性質を持ちます。
- 一番左の桁は、2 か 3 か ５ か ７ となる。
これは、最後に残る数字が１桁の素数となるためである。 - それ以降の桁は、1 か ３ か ７ か ９ となる。
偶数は２の倍数となり、5は5の倍数となるためである。
木構造を使って、右切り捨て可能素数をすべて求めてみました。
0 から開始して、一桁右に加えて素数になる 2、3、5、7 を枝に加えます。次に 2 に一桁右に加えて素数になる 23、29 を 2 の枝に加えます。同じように 23 に一桁右に加えて素数になる 233 と 239 を 23 の枝に加えます。どのように一桁右に加えても素数とならない場合、末端（葉）となります。
プログラムは、C++ で書きました。make_rtp で右切り捨て可能素数の木を作って、dfs で読み出し Vector 型の変数 rtp に push します。rtp は、right-truncatable prime を意味します。
最後に rtp をソートして、0 を除いて出力します。
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int is_prime(int n)
{
int answer = 1;
int i;
if (n <= 1) {
answer = 0;
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}
map<int, vector<int>> p;
map<int, bool> seen;
void make_rtp(int n)
{
for (int i = 0; i <= 9; ++i) {
if (is_prime(n * 10 + i) == 1) {
p[n].push_back(n * 10 + i);
make_rtp(n * 10 + i);
}
}
}
vector<int> rtp;
void dfs(int n)
{
seen[n] = true;
rtp.push_back(n);
for (auto next_n : p[n]) {
if (!seen[next_n]) {
dfs(next_n);
}
}
}
int main()
{
make_rtp(0);
dfs(0);
sort(rtp.begin(), rtp.end());
for (auto e : rtp) {
if (e != 0) {
printf("%8d\n", e);
}
}
return 0;
}全部で83個の素数が出力されて、一番大きな右切り捨て可能素数は、73939133 でした。
最後に
最初の枝は、2、3、5、7 ですが、どれも8桁までは見つかりました。
右切り捨て可能素数は、最初の桁を除けば、1、3、7、9 の4種類しかありません。一方、左切り捨て可能素数は、左に加える桁は、1から9まで9種類の選択肢があります。このため、最大の左切り捨て可能素数は、357686312646216567629137（24桁）のように右切り捨て可能素数の最大値よりもかなり大きくなっています。
素朴に1億以上、10億未満（9桁）に右切り捨て可能素数ないことを示せば、8桁が最大になることは分かります。ただし、木構造を使った今回のプログラムは、計算量がとても少なくなっています。またプログラムを楽しむことができました。
右切り捨て可能素数
今回の紹介したプログラムの出力です。83個あります。
2
3
5
7
23
29
31
37
53
59
71
73
79
233
239
293
311
313
317
373
379
593
599
719
733
739
797
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
23333
23339
23399
23993
29399
31193
31379
37337
37339
37397
59393
59399
71933
73331
73939
233993
239933
293999
373379
373393
593933
593993
719333
739391
739393
739397
739399
2339933
2399333
2939999
3733799
5939333
7393913
7393931
7393933
23399339
29399999
37337999
59393339
73939133
