prog.pl

#!/usr/bin/perl

use 5.014;
use ntheory qw(:all);
use experimental qw(signatures);

use Memoize qw(memoize);

memoize('a');

sub a ($n, $base) {

    return 1 if ($n == 0);

    my $t = a($n - 1, $base);
    for (my $k = $t + 1 ; ; ++$k) {
        if (powmod($base, $k - 1, $t * $k) == 1) {
            return $k;
        }
    }
}

foreach my $base (2 .. 30) {

    my @list;
    my $k = a(0, $base);

    for (my $n = 0 ; $k < 1e5 ; ++$n) {
        $k = a($n, $base);
        push @list, $k;
    }

    my $prime_count = scalar grep { is_prime($_) } @list;
    my $total_count = scalar @list;

    printf("[%.2f%% primes] a(%2d) = {%s, ...}\n", $prime_count / $total_count * 100, $base, join(', ', @list), ", ...}");
}

__END__
[94.12% primes] a( 2) = {1, 3, 5, 13, 37, 73, 109, 181, 541, 1621, 4861, 9721, 10531, 17551, 29251, 87751, 526501, ...}
[94.44% primes] a( 3) = {1, 2, 5, 13, 19, 37, 73, 97, 193, 241, 601, 751, 2251, 3001, 4001, 16001, 96001, 160001, ...}
[90.48% primes] a( 4) = {1, 3, 5, 7, 13, 19, 37, 73, 91, 97, 193, 241, 277, 461, 691, 1151, 14951, 15641, 70381, 78031, 156061, ...}
[92.86% primes] a( 5) = {1, 2, 3, 7, 13, 17, 97, 193, 577, 1153, 3457, 10369, 28513, 228097, ...}
[94.74% primes] a( 6) = {1, 5, 7, 11, 31, 37, 41, 241, 281, 337, 449, 2689, 10753, 12289, 18433, 19457, 58369, 87553, 109441, ...}
[90.00% primes] a( 7) = {1, 2, 3, 5, 13, 25, 29, 43, 61, 181, 193, 241, 1201, 1217, 7297, 12161, 13681, 27361, 54721, 109441, ...}
[71.43% primes] a( 8) = {1, 3, 5, 9, 11, 21, 23, 45, 53, 105, 109, 133, 139, 231, 241, 257, 273, 277, 461, 1381, 3221, 5153, 6833, 27329, 40993, 51241, 55511, 222041, ...}
[77.78% primes] a( 9) = {1, 2, 4, 5, 7, 13, 19, 28, 31, 61, 71, 211, 421, 631, 946, 1051, 1471, 2647, 10585, 10627, 11551, 15401, 15841, 15901, 47701, 71551, 157411, ...}
[95.24% primes] a(10) = {1, 3, 7, 13, 19, 37, 43, 127, 211, 241, 271, 281, 337, 673, 2017, 12097, 20161, 21841, 54601, 81901, 819001, ...}
[88.24% primes] a(11) = {1, 2, 3, 5, 7, 10, 13, 37, 43, 71, 211, 281, 2521, 2633, 5923, 23689, 165817, ...}
[88.89% primes] a(12) = {1, 5, 13, 17, 65, 73, 109, 163, 487, 541, 811, 1297, 1621, 1783, 5347, 26731, 80191, 106921, ...}
[84.21% primes] a(13) = {1, 2, 3, 4, 5, 17, 21, 23, 67, 199, 397, 2377, 7129, 7393, 8009, 8581, 25741, 38611, 115831, ...}
[94.44% primes] a(14) = {1, 3, 5, 11, 31, 61, 67, 89, 353, 1409, 2113, 6337, 7129, 28513, 64153, 81649, 95257, 238141, ...}
[94.12% primes] a(15) = {1, 2, 7, 11, 31, 41, 241, 271, 541, 577, 1153, 3457, 10369, 12097, 72577, 96769, 100801, ...}
[86.96% primes] a(16) = {1, 3, 5, 7, 13, 19, 37, 73, 91, 97, 109, 127, 197, 491, 1471, 5881, 7351, 10501, 21001, 22751, 68251, 68771, 123787, ...}
[91.30% primes] a(17) = {1, 2, 3, 5, 9, 11, 31, 61, 181, 397, 661, 991, 1123, 1871, 7481, 10099, 11287, 14851, 16633, 55441, 76231, 97021, 145531, ...}
[80.00% primes] a(18) = {1, 5, 13, 17, 19, 23, 67, 133, 139, 277, 829, 1105, 1109, 3325, 3361, 3571, 10711, 12241, 16831, 23563, 43759, 47737, 59671, 70201, 105301, ...}
[90.48% primes] a(19) = {1, 2, 3, 5, 7, 13, 37, 73, 109, 181, 193, 577, 673, 2017, 4033, 4177, 5569, 22273, 33409, 41761, 375841, ...}
[84.21% primes] a(20) = {1, 3, 7, 11, 21, 23, 67, 133, 137, 409, 613, 3061, 3163, 18973, 23189, 27281, 27941, 41911, 125731, ...}
[87.50% primes] a(21) = {1, 2, 5, 11, 13, 17, 29, 85, 89, 221, 229, 457, 761, 1901, 2281, 3041, 4561, 6841, 13681, 14593, 43777, 87553, 94849, 109441, ...}
[88.89% primes] a(22) = {1, 3, 5, 13, 19, 37, 73, 89, 199, 397, 2377, 7129, 8911, 9109, 18217, 20287, 60859, 243433, ...}
[95.45% primes] a(23) = {1, 2, 3, 5, 13, 19, 37, 61, 101, 151, 181, 541, 811, 1621, 2161, 6481, 9721, 19441, 58321, 64153, 80191, 240571, ...}
[88.89% primes] a(24) = {1, 5, 7, 13, 25, 29, 43, 127, 163, 325, 337, 673, 1009, 1051, 4201, 6301, 10501, 19501, 19801, 25301, 37951, 44851, 45751, 47251, 47701, 95401, 111301, ...}
[77.27% primes] a(25) = {1, 2, 3, 4, 6, 7, 13, 17, 41, 61, 91, 97, 193, 577, 1153, 1729, 1747, 8731, 10477, 47143, 78571, 104761, ...}
[75.00% primes] a(26) = {1, 3, 5, 7, 19, 25, 27, 29, 113, 225, 227, 1583, 6329, 63281, 71191, 142381, ...}
[83.33% primes] a(27) = {1, 2, 5, 13, 17, 65, 73, 89, 353, 1409, 9857, 10753, 12545, 12577, 23057, 25153, 54497, 544961, ...}
[88.89% primes] a(28) = {1, 3, 5, 9, 11, 31, 61, 101, 401, 601, 1201, 1801, 2161, 6481, 19441, 58321, 59779, 119557, ...}
[85.00% primes] a(29) = {1, 2, 3, 5, 7, 11, 21, 23, 67, 73, 433, 1297, 2593, 5185, 5233, 6977, 20929, 26161, 52321, 117721, ...}
[85.00% primes] a(30) = {1, 7, 13, 19, 31, 37, 73, 97, 193, 577, 1153, 1537, 1549, 3097, 3169, 4357, 8713, 34849, 47917, 407287, ...}