prime_abundant_sequences.pl

#!/usr/bin/perl

# For a fixed integer base b > 1,
#   a(n) is the smallest k > a(n-1) such that b^(k-1) == 1 (mod a(n-1)*k), with a(0) = 1.

# Thomas Ordowski's conjecture:
#   For any integer base b > 1, a(n) is prime for almost all n.

# See also:
#   https://oeis.org/A306826

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

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] b = %2d, a(n) = {%s, ...}\n",
           $prime_count / $total_count * 100,
           $base, join(', ', @list),
           ", ...}");
}

__END__
[94.44% primes] b =  2, a(n) = {1, 3, 5, 13, 37, 73, 109, 181, 541, 1621, 4861, 9721, 10531, 17551, 29251, 87751, 526501, 3159001, ...}
[94.74% primes] b =  3, a(n) = {1, 2, 5, 13, 19, 37, 73, 97, 193, 241, 601, 751, 2251, 3001, 4001, 16001, 96001, 160001, 1120001, ...}
[92.59% primes] b =  4, a(n) = {1, 3, 5, 7, 13, 19, 37, 73, 91, 97, 193, 241, 277, 461, 691, 1151, 14951, 15641, 70381, 78031, 156061, 312121, 343333, 362407, 724813, 895357, 1044583, ...}
[93.75% primes] b =  5, a(n) = {1, 2, 3, 7, 13, 17, 97, 193, 577, 1153, 3457, 10369, 28513, 228097, 456193, 5930497, ...}
[96.00% primes] b =  6, a(n) = {1, 5, 7, 11, 31, 37, 41, 241, 281, 337, 449, 2689, 10753, 12289, 18433, 19457, 58369, 87553, 109441, 127681, 255361, 383041, 478801, 538651, 1077301, ...}
[92.00% primes] b =  7, a(n) = {1, 2, 3, 5, 13, 25, 29, 43, 61, 181, 193, 241, 1201, 1217, 7297, 12161, 13681, 27361, 54721, 109441, 115201, 172801, 345601, 432001, 2160001, ...}
[74.19% primes] b =  8, a(n) = {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, 499591, 999181, 1379821, ...}
[81.82% primes] b =  9, a(n) = {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, 174901, 262351, 524701, 787051, 891991, 1783981, ...}
[95.65% primes] b = 10, a(n) = {1, 3, 7, 13, 19, 37, 43, 127, 211, 241, 271, 281, 337, 673, 2017, 12097, 20161, 21841, 54601, 81901, 819001, 955501, 4777501, ...}
[89.47% primes] b = 11, a(n) = {1, 2, 3, 5, 7, 10, 13, 37, 43, 71, 211, 281, 2521, 2633, 5923, 23689, 165817, 497449, 1160713, ...}
[91.30% primes] b = 12, a(n) = {1, 5, 13, 17, 65, 73, 109, 163, 487, 541, 811, 1297, 1621, 1783, 5347, 26731, 80191, 106921, 187111, 192781, 289171, 867511, 1561519, ...}
[86.36% primes] b = 13, a(n) = {1, 2, 3, 4, 5, 17, 21, 23, 67, 199, 397, 2377, 7129, 7393, 8009, 8581, 25741, 38611, 115831, 231661, 463321, 1158301, ...}
[94.74% primes] b = 14, a(n) = {1, 3, 5, 11, 31, 61, 67, 89, 353, 1409, 2113, 6337, 7129, 28513, 64153, 81649, 95257, 238141, 1190701, ...}
[95.45% primes] b = 15, a(n) = {1, 2, 7, 11, 31, 41, 241, 271, 541, 577, 1153, 3457, 10369, 12097, 72577, 96769, 100801, 102001, 153001, 191251, 212501, 1020001, ...}
[88.46% primes] b = 16, a(n) = {1, 3, 5, 7, 13, 19, 37, 73, 91, 97, 109, 127, 197, 491, 1471, 5881, 7351, 10501, 21001, 22751, 68251, 68771, 123787, 165049, 174571, 1396561, ...}
[92.00% primes] b = 17, a(n) = {1, 2, 3, 5, 9, 11, 31, 61, 181, 397, 661, 991, 1123, 1871, 7481, 10099, 11287, 14851, 16633, 55441, 76231, 97021, 145531, 436591, 1018711, ...}
[82.76% primes] b = 18, a(n) = {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, 105319, 351061, 936161, 7957361, ...}
[91.67% primes] b = 19, a(n) = {1, 2, 3, 5, 7, 13, 37, 73, 109, 181, 193, 577, 673, 2017, 4033, 4177, 5569, 22273, 33409, 41761, 375841, 501121, 534529, 4810753, ...}
[85.71% primes] b = 20, a(n) = {1, 3, 7, 11, 21, 23, 67, 133, 137, 409, 613, 3061, 3163, 18973, 23189, 27281, 27941, 41911, 125731, 176023, 1408177, ...}
[90.00% primes] b = 21, a(n) = {1, 2, 5, 11, 13, 17, 29, 85, 89, 221, 229, 457, 761, 1901, 2281, 3041, 4561, 6841, 13681, 14593, 43777, 87553, 94849, 109441, 255361, 319201, 322001, 386401, 418601, 1255801, ...}
[90.48% primes] b = 22, a(n) = {1, 3, 5, 13, 19, 37, 73, 89, 199, 397, 2377, 7129, 8911, 9109, 18217, 20287, 60859, 243433, 426007, 852013, 2130031, ...}
[96.15% primes] b = 23, a(n) = {1, 2, 3, 5, 13, 19, 37, 61, 101, 151, 181, 541, 811, 1621, 2161, 6481, 9721, 19441, 58321, 64153, 80191, 240571, 267301, 534601, 588061, 1176121, ...}
[90.00% primes] b = 24, a(n) = {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, 222601, 296801, 1187201, ...}
[80.00% primes] b = 25, a(n) = {1, 2, 3, 4, 6, 7, 13, 17, 41, 61, 91, 97, 193, 577, 1153, 1729, 1747, 8731, 10477, 47143, 78571, 104761, 115237, 403327, 1209979, ...}
[80.95% primes] b = 26, a(n) = {1, 3, 5, 7, 19, 25, 27, 29, 113, 225, 227, 1583, 6329, 63281, 71191, 142381, 355951, 457651, 813601, 915301, 1525501, ...}
[84.21% primes] b = 27, a(n) = {1, 2, 5, 13, 17, 65, 73, 89, 353, 1409, 9857, 10753, 12545, 12577, 23057, 25153, 54497, 544961, 1634881, ...}
[90.00% primes] b = 28, a(n) = {1, 3, 5, 9, 11, 31, 61, 101, 401, 601, 1201, 1801, 2161, 6481, 19441, 58321, 59779, 119557, 358669, 2152009, ...}
[86.96% primes] b = 29, a(n) = {1, 2, 3, 5, 7, 11, 21, 23, 67, 73, 433, 1297, 2593, 5185, 5233, 6977, 20929, 26161, 52321, 117721, 164809, 195329, 1171969, ...}
[85.71% primes] b = 30, a(n) = {1, 7, 13, 19, 31, 37, 73, 97, 193, 577, 1153, 1537, 1549, 3097, 3169, 4357, 8713, 34849, 47917, 407287, 6109291, ...}