eldar_carmichael_numbers_cached.pl

#!/usr/bin/perl

# Carmichael numbers n = p1 * p2 * ... * pk, such that nextprime(p1) * nextprime(p2) * ... * nextprime(pk) is also a Carmichael numbers.
# https://oeis.org/A346569

# Sequence defined by Amiram Eldar.

# Known terms:
#   938531360353681, 6178246534322281, 518705522457928921, 7019247908645553241, 16242056799655920481

# Upper-bound for the next term:
#   a(6) <= 94812683932464811561

# A term with 4 prime factors, is:
#  9584146525723596902470058833132261

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 $table         = retrieve($storable_file);

{
    my $nm1 = Math::GMPz::Rmpz_init();
    my $pm1 = Math::GMPz::Rmpz_init();

    sub my_is_carmichael_faster ($n, $factors) {
        Math::GMPz::Rmpz_set_str($nm1, $n, 10);
        Math::GMPz::Rmpz_sub_ui($nm1, $nm1, 1);
        return if not vecall {
            ($_ < ~0) ? Math::GMPz::Rmpz_divisible_ui_p($nm1, $_ - 1) : do {
                Math::GMPz::Rmpz_set_str($pm1, $_, 10);
                Math::GMPz::Rmpz_sub_ui($pm1, $pm1, 1);
                Math::GMPz::Rmpz_divisible_p($nm1, $pm1);
            }
        }
        @$factors;
        return 1;
    }
}

my %seen;

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

    #next if (length($key) > 100);

    my @f = split(' ', $value);

    my @factors_next = map { next_prime($_) } @f;
    my $prod_next    = Math::Prime::Util::GMP::vecprod(@factors_next);

    if (my_is_carmichael_faster($prod_next, \@factors_next)) {
        say $key if !$seen{$key}++;
    }

    next if ($f[0] eq '3');

    my @factors_prev = map { prev_prime($_) } @f;
    my $prod_prev    = Math::Prime::Util::GMP::vecprod(@factors_prev);

    if (my_is_carmichael_faster($prod_prev, \@factors_prev)) {
        say $prod_prev if !$seen{$prod_prev}++;
    }
}

__END__

# Terms > 2^64 (with possible gaps):

94812683932464811561
94986212971063089241
408133613144935002601
418441276466266605481
453648717063017803081
556606627235843071681
1140359076998537247001
1265680279562578262641
1951809736309861212721
5980564124141858706241
6137806881428350172281
6326492388236115060241
24891238112934056055121
28095853904206547181841
40434555297165999259681
48261260980874938077721
58206535499765403272161
63828869096059598070361
87338832489985155998761
106302355746814524300121
119960673586039007118361
216537148874914099116121
322566378380150158090801
415299852143037277782841
420624230680346219759161
506716726354626038450041
553067290322607167033401
595887226009666047980641
601479589681134271811161
624233572149736191180961
937637515201230527931001
3579850161227182901792761
12489938127929055799017361
47430522716235575473870561
62119836345479971567903561
184583159587760857018057441
2963493415698289948011317401
7814789287696783820365397281
10849762448893493552144917285561
14575673610630038251625123200321
9584146525723596902470058833132261
370485652148454262193196862967213221
8490838069761166109786463598726104481
4096504672640940553827263914489012599841
6990741760990734881545992440694211925461
12215958599011113260975124155377843660801
229616858320118848756413304553515547584981
241284319906479251322446980767146978527681
793099737907814193337332941999794792993621
1175634565417233632813259537377605462400641
5766792510071815411263171890434895414851342305997584006734761

# Related sequence: Carmichael numbers n such that next_prime(p)-1 | n-1 for every p|n.

18162001
1928376089641
2763418331521
7414899695281
115347658567681
235913416588081
274783185600001
379873505975041
633036184981201
1771238725557841
2118721613823361
3490904385848881
5331664088593921
8730276621066001
10218586671216001
11527983190508401
12691843389308161
13518639051160321
14201024890409281
34969972713318721
48720697311797281
49544666061770881
64524870728398081
86398337105388001
108716045132217601
109629798901983361
155913594718583521
179762516444427841
237127022999475841
299637882714083761
320931787486353121
429341988888933121
617327766476300881
654801288745968001
730527207720710401
860180756031273601
866443931475202081

# Larger term:

34940221654286551681