前回は、Project Euler で紹介されている問題37を解いてみました。今回は、条件を満たす素数が11個しかないことを示します。
再掲載 Project Euler 問題37（切り捨て可能素数）
3797 という数字には興味深い性質があります。 それ自体が素数であることに加えて、数字を左から右に削除し、各段階で素数を得ることができます：3797、797、97、および 7。同様に、右から左に削除しても素数を得ることができます： 3797、379、37、および 3 です。
左から右へも右から左へも切り捨て可能な素数は 11 個ある。その素数の合計を求めよ。
注: 2、3、5、および 7 は、切り捨て可能な素数と考えません。
考察
100万未満の切り捨て可能な素数の最大であるものは、739397 でした。結果的に 739397 が最大となることを計算で示します。
素朴に、6桁の数まであるのだから7桁の数に該当する素数がなければ、739397 が最大値なのでは？と考えたとします。
これには、明確な反例があり、739397 より小さい直前の素数は 3797 です。4桁と6桁はありますが、5桁の該当する素数がありません。左かつ右切り捨て可能な素数を求めていくため、このようなことが発生します。左切り捨て可能な素数だけを考えれば、ある桁数の左切り捨て可能な素数がなければ、それより大きな左切り捨て可能な素数はありません。
右切り捨て可能な素数にも同じことが言えます。
なにか、この問題を解くための制約が設定できないでしょうか。
Wikipedia に「切り捨て可能素数」というそのままのページがあります。以下の記述があります。
- 左切り捨て可能な最大の素数 357686312646216567629137
- 右切り捨て可能な最大の素数 73939133
この問題は、左かつ右切り捨て可能な素数を求める問題であるため、右切り捨て可能な最大の素数より大きくなることはありません。
このため、10 以上1億未満の自然数に対して左かつ右切り捨て可能な素数か調べれば分かります。
全体の C プログラムは、以下となります。is_prime の呼び出しが多いため、エラトステネスの篩を使うものに置き換えました（道具箱参照）。このプログラムは計算機の環境によっては、数分かかるかもしれません。
#include <stdio.h>
#define N 100000000
unsigned char is_prime_table[N+1];
#define is_prime(n) (is_prime_table[(n)])
void generate_is_prime_table(int n)
{
int i, j;
for (i = 2; i <= n; ++i) {
is_prime_table[i] = 1;
}
for (i = 2; i * i <= n; ++i) {
if (is_prime_table[i] == 1) {
for (j = i + i; j <= n; j += i) {
is_prime_table[j] = 0;
}
}
}
return;
}
int is_satisfied(int number)
{
int ret_val = 1;
int original, digits;
int i, mask, check_number;
original = number;
digits = 0;
while (number > 0) {
++digits;
number = number / 10;
}
mask = 1;
for (i = 2; i <= digits; ++i) {
mask = mask * 10;
}
if (is_prime(original) == 0) {
ret_val = 0;
}
check_number = original % mask;
while (mask >= 10) {
if (is_prime(check_number) == 0) {
ret_val = 0;
break;
}
mask = mask / 10;
check_number = original % mask;
}
check_number = original / 10;
while (check_number > 0) {
if (is_prime(check_number) == 0) {
ret_val = 0;
break;
}
check_number = check_number / 10;
}
return ret_val;
}
int main(void)
{
int n;
generate_is_prime_table(N);
for (n = 10; n < N; ++n) {
if (is_satisfied(n) == 1) {
printf("%d\n", n);
}
}
return 0;
}1億まで範囲を増やしても、11個しか素数が出力されませんでした。変わらず一番大きな素数は、739397 でした。計算の結果ではありますが、左かつ右切り捨て可能な最大の素数は、739397 であることが分かりました。
最後に
前回は、（適当に）100万まで計算して解答を求めていましたが、今回は、前回の結果が正しいことを計算で示しました。「右切り捨て可能な最大な素数が 73939133 である」ことを使いました。別の記事でこれを計算で示しました。
引き続き、Project Euler の問題を紹介していきます。
