Math Battle [ 0339: emirp 探し ]

[ 0339: emirp 探し ]


[ 星楊令さんの出題 ]

数学には、いろいろ遊びの分野があります。 エマープ(emirp)とは 素数でありかつ逆から数字を読むと元の数とは異なる素数 (prime) になる自然数のことです。Prime を逆から読むと emirp ですね。 あくまでも十進表記で成り立つことですが。

例えば 1097 は素数で、かつ 7901 も素数であるためこの 2 つの数はエマープです。エマープと回文数になっている素数を合わせたもの (つまり、逆から読んでも素数である素数全体) を「回文素数 (palindromic prime)」ということもあります。

なお、エマープは無限に存在するかどうかはまだ数学で確かめられてはいませんが、 これまでに知られている最も大きなエマープは 2007 年 10 月に Jens Kruse Andersen が発見した 1010006 + 941992101 * 104999 + 1 です。 どうやって探したのでしょうね?

さて、問題です。10000 までの範囲で emirp を全部探すプログラムを作ってください。 実行結果も添えて。


[ 浅見多絵さんの回答 ]

楊令さん、できました。次のような Perl プログラムです。
(一部訂正: もとの数と逆順の数が同じ場合を排除)

#!/usr/local/bin/perl

@primes = ();
$n_primes = 0;
@emirps = ();
$n_emirps = 0;

for ($n=2; $n<=10000; $n++) {
 my $n2;

 next unless is_prime($n);
 $primes[$n_primes++] = $n;
 $n2 = reverse_number($n);

 if ($n != $n2 && is_prime($n2)) {
  $emirps[$n_emirps++] = $n;
 }
}
printf("Found %d emirps in %d primes.\n",
 $n_emirps, $n_primes);

for ($j=0; $j<$n_emirps; $j++) {
 printf("%4d | %4d\n",
  $emirps[$j], reverse_number(@emirps[$j]));
}
sub reverse_number($n) {
 my ($n) = @_;
 my $str, @digits, $n2;

 $str = sprintf("%d", $n);
 @digits = split(//, $str);
 @digits = reverse @digits;
 $str = join('', @digits);
 $n2 = $str + 0; # 数値に変換する。
 return($n2);
}
sub is_prime($n) {
 my ($n) = @_;
 my $j;

 return 1 if ($n == 2); # true

 for ($j=0; $j<$n_primes; $j++) {
  last if ($n < $primes[$j]**2);
  if (($n % $primes[$j]) == 0) {
   return 0; # false
  }
 }
 return 1; #true
}

  • 素数が何もない状態から始めます。
    これまでに見つかった素数で割った剰余 (%) がゼロであれば素数ではありません。 このチェックは対象の数の平方根あたりまでの素数でおこないます。 チェックをパスすれば素数です。

  • 2 に対してはそれまでに見つかった素数がないため、そのまま最初の素数になります。 3 は 3 < 22 なのでそのまま素数チェックをバスします。 4 は 4 = 22 なので 2 で割った剰余のチェックをし、 ゼロなので素数でないとしてはじかれます。

    以下同様。

  • 見つかった素数に対しては 数字を逆順にした数と同じかどうかをチェックします。 同じ (対称) であれば emirp ではありません。 同じでなければ逆順の数に対して素数かどうかのチェックをおこないます。 これも素数であれば emirp です。

実行結果 (一部) は以下のとおりでした。


Found 240 emirps in 1229 primes.
  13 |   31
  17 |   71
  31 |   13
  37 |   73
  71 |   17
  73 |   37
  79 |   97
  97 |   79
 107 |  701
 113 |  311
 149 |  941
 157 |  751
 167 |  761
 179 |  971
 199 |  991
 311 |  113
 337 |  733
 347 |  743
 359 |  953
 389 |  983
 701 |  107
 709 |  907
.....
9721 | 1279
9749 | 9479
9769 | 9679
9781 | 1879
9787 | 7879
9791 | 1979
9803 | 3089
9833 | 3389
9857 | 7589
9871 | 1789
9883 | 3889
9923 | 3299
9931 | 1399
9941 | 1499
9967 | 7699

[ 星楊令さんのコメント ]

多絵さん、ありがとうございます。

プログラムは明快に書かれており、説明もわかりやすいです。
これでいいと思います。


[ 広世正憲君のコメント ]

なるほど、うまいやりかたですね。

Singularity が起きるといわれる 2045 年までの任意の年の 素数日 を求める場合は sqrt(20451231) が約 4522.3 ですから 4522 までの範囲の素数をあらかじめ用意しておけばいいですね。

614 個見つかりましたが、これを配列としてソースコードに入れると行数を食いますから そのつど求めてもあっという間に準備できます。

その年がうるう年かどうかは 「西向く侍」を参考にします。

[ 0341: 次の記事 ]

[ 0340: 素数日プログラム ]

[ 0339: emirp 探し ]

[ 0338: 0331の解きなおし ]

[ 0337: ubuntu 20.04 へ upgrade ]

[ 0336: πの近似計算 ]

[ 0335: 0253 の振り返り ]

[ 0334: Data Camp Python ]

[ 0333: 原始ピタゴラス数をさがす ]

[ 0332: LaTex の使いかた ]

[ 0331: 青い三角形の面積 ]

[ 0330: 長方形の幅 ]

[ 0329: 三角関数の関数の最大最小 ]

[ 0328: IMO 過去問 9 ]

[ 0327: 1+2+3+...+無限 ]

[ 0326: 2分木 sort も含めた性能比較 ]

[ 0325: 最悪ケースでの sort 比較 ]

[ 0324: 0307の回答 ④ ]

[ 0323: 0307の回答 ③ ]

[ 0322: 0307の回答 ② ]

[ 0321: 0307の回答 ① ]

[ 0320: 前の記事 ]

[ トップページへ ]