experimental-projects/pseudoprimes/programs/smallest_carmichael-kronecker_with_n_factors_cached.pl

#!/usr/bin/perl

# Least Carmichael number k with n prime factors, having kronecker(5,p) = -1 for all primes p|k.

use 5.020;
use strict;
use warnings;

use Storable;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);

my $storable_file = "cache/factors-carmichael.storable";
my $carmichael    = retrieve($storable_file);

my %table;

while (my ($key, $value) = each %$carmichael) {

    #kronecker(5,$key) == -1 or next;

    my @factors = split(' ', $value);
    my $count   = scalar(@factors);

    next if ($count < 10);

    (vecall { kronecker(5, $_) == -1 } @factors) || next;

    my $n = Math::GMPz->new($key);

    if (exists $table{$count}) {
        next if ($table{$count} < $n);
    }

    $table{$count} = $n;
    say "a($count) <= $n";
}

say "\n\nFinal results:\n";

foreach my $k (sort { $a <=> $b } keys %table) {
    printf("a(%3d) <= %s\n", $k, $table{$k});
}

__END__
a( 10) <= 30013487338223743201
a( 11) <= 1829087313861474862273
a( 12) <= 337695413426013716238529
a( 13) <= 140865031766932330246183873
a( 14) <= 17691024922368632614422453889
a( 15) <= 12645317336903274624630026592673
a( 16) <= 14196649107618758204011845543686401
a( 17) <= 2309173143848017114041309867010434433
a( 18) <= 171170567401280448697446558241918959285889
a( 19) <= 454721150229403852923795648560187941931377857
a( 20) <= 4382788616140887860370115516185831010562321782778881
a( 21) <= 2626800425489709477930098102007105331062454960351666428673
a( 22) <= 31658664340124722025021255962040913803802258388443841
a( 23) <= 18253657709236091851020680698825663958254894734833784512257
a( 24) <= 3821039575948030998109446373346815931263615548467217529093487041
a( 25) <= 5844072823238808772175666889302356778676396227293230888934760826636097
a( 26) <= 14428759159921264771078877192963558684496035880861322342035125339149441
a( 27) <= 6406849764685589284232513910437799273390638299815902026671631413173626460287052130298179457
a( 30) <= 2084993061635761846083487160555208993471712785721364889865962052418053348475785921
a( 32) <= 151704619133522715319049708005625810072182925416121051478888363652326509169784449807067309886042544289
a( 34) <= 43794076876617570369265069381312850224497942122128841005399616612583072330123249170271312171267939194401
a( 36) <= 137515397146132022936512072656969444034166833375227584395369640371849509821936093626221551403233835573154592635162561
a( 38) <= 1552707294557653966357865392395190405491528363741027177012246612936774490051275293629397402062078531602898747918580511798362217601