大きな整数を探せ - inamori’s diary

http://blog.mf-davinci.com/mori_log/archives/2008/01/post_1613.php

71、701、7001、…、700000001という自然数が素数かどうか調べると、
8つ中6つが素数なのだという。

多倍長整数はPerlで簡単に扱えるので（遅いが）、調べてみた。



use bigint;
for my $i(1..20) {

    my $n = 7*10**$i + 1;

    print $n, " ", (isprime($n) ? "○" : "×"), "\n";

}
sub isprime {

    my ($n) = @_;

    my $limit = sqrt($n);

    return 0 if $n % 2 == 0;

    for(my $p = 3; $p <= $limit; $p += 2) {

        return 0 if $n % $p == 0;

    }

    return 1;

}



71 ○

701 ○

7001 ○

70001 ○

700001 ○

7000001 ×

70000001 ×

700000001 ○

7000000001 ○

70000000001 ×

700000000001 ×

7000000000001 ×

70000000000001 ×

700000000000001 ×

7000000000000001 ×

70000000000000001 ×

700000000000000001 ×

7000000000000000001 ×

70000000000000000001 ×

700000000000000000001 ×

次が素数で、あとは調べた範囲では合成数という結果に終わった。

これは要するに、



	a * bⁿ + c

という形で、素数になる自然数が多い組合せは？
という問題になるだろう。
(a, b, c) = (1, 2, -1)ならメルセンヌ数である。
メルセンヌ数は容易な素数判定法があるので、
巨大な素数が発券された、というのは必ずメルセンヌ数になる。
上の形なら、同様に容易な素数判定法は見つからないだろうか。