experimental-projects/pseudoprimes/programs/carmichael_gpf(p-1) = prime(n).pl

#!/usr/bin/perl

# a(n) is the smallest Carmichael number such that gpf(p-1) = prime(n) for all prime factors p of a(n).

use 5.020;
use strict;
use warnings;
use experimental qw(signatures);

use ntheory    qw(:all);
use List::Util qw(uniq);

my %seen;
my %table;

while (<>) {
    next if /^\h*#/;
    /\S/ or next;
    my $n = (split(' ', $_))[-1];

    $n || next;

    next if ($n > 1e15);
    is_carmichael($n) or next;
    next if $seen{$n}++;

    my @gpf = uniq(map { (factor($_ - 1))[-1] } factor($n));

    if (@gpf == 1) {
        my $p = $gpf[0];
        $table{$p} //= $n;
        if ($n < $table{$p}) {
            $table{$p} = $n;
        }
    }
}

foreach my $p (sort { $a <=> $b } keys %table) {
    my $n = prime_count($p);
    say "a($n) = $table{$p}";
}

__END__

# Upper-bounds < 10^15

a(2) = 1729
a(3) = 252601
a(4) = 1152271
a(5) = 1615681
a(6) = 4335241
a(7) = 172947529
a(8) = 214852609
a(9) = 79624621
a(10) = 178837201
a(11) = 775368901
a(12) = 686059921
a(13) = 985052881
a(14) = 5781222721
a(15) = 10277275681
a(16) = 84350561
a(17) = 5255104513
a(18) = 492559141
a(19) = 74340674101
a(20) = 9293756581
a(21) = 1200778753
a(22) = 129971289169
a(23) = 2230305949
a(24) = 851703301
a(25) = 8714965001
a(26) = 6693621481
a(27) = 3313196881
a(28) = 704209440481
a(29) = 537396116401
a(30) = 2436691321
a(31) = 74500799437
a(32) = 542497201
a(33) = 8346731851
a(34) = 39283501681
a(35) = 171615172321
a(36) = 114012594697
a(37) = 401397353281
a(38) = 496950008129
a(39) = 3091175755489
a(40) = 42383927401
a(41) = 88183003921
a(42) = 76940276401
a(43) = 516441599521
a(44) = 1444635316441
a(45) = 2246625745201
a(46) = 46601368669
a(47) = 5526520971721
a(48) = 1797002211241
a(49) = 6169135851841
a(50) = 545009067541
a(51) = 49237316749
a(52) = 83946864769
a(53) = 18500666251
a(54) = 54519328481
a(55) = 1849275141841
a(56) = 15210276812821
a(57) = 207222530621
a(58) = 60246018673
a(59) = 68926289491
a(60) = 96464987884231
a(61) = 6032781519073
a(62) = 97887454669
a(63) = 155706912481
a(64) = 663162938677
a(65) = 835085057941
a(66) = 37371065373211
a(67) = 191614761361
a(68) = 110296864801
a(69) = 469593692569
a(70) = 116965170676481
a(71) = 124711042468951
a(72) = 13358856700001
a(73) = 11109642966241
a(74) = 112241637539329
a(75) = 15239647744441
a(76) = 9322668177409
a(77) = 89726324722273
a(78) = 40144845106081
a(79) = 585210826621
a(80) = 210359235841
a(81) = 1101375141511
a(82) = 82932179259511
a(83) = 808025490721
a(84) = 155999871721
a(85) = 778373466563701
a(86) = 635075174497
a(87) = 3711846239473
a(88) = 942121181242081
a(89) = 4328349874081
a(90) = 4460497633489
a(91) = 23570421789223
a(92) = 675518387329
a(93) = 76897431373121
a(94) = 34138047673
a(95) = 14351225648761
a(96) = 342267565249
a(97) = 606244450001
a(99) = 7472532278353
a(100) = 73881755325361
a(102) = 80535816022481
a(103) = 61251633643201
a(104) = 1671721833853
a(105) = 108099149330593
a(106) = 2739572924617
a(107) = 5811733744867
a(108) = 7689096933451
a(109) = 138317418049441
a(110) = 1407301287481
a(111) = 1933026463201
a(112) = 64278632045431
a(113) = 667028583421201
a(114) = 9035899110701
a(115) = 6513448976101
a(116) = 63280622521
a(117) = 542904805653211
a(118) = 189557159803021
a(119) = 9265006341361
a(120) = 144377609419
a(121) = 14353280005201
a(122) = 111829787722801
a(123) = 236469841032097
a(124) = 4485339189841
a(125) = 2217790426321
a(126) = 49336662504403
a(127) = 6691635307237
a(128) = 2803378414477
a(129) = 2066548448161
a(130) = 557281844263153
a(131) = 5426319533881
a(133) = 915245066821
a(134) = 15181505298649
a(135) = 1333189866793
a(137) = 7982920590961
a(138) = 353782889243281
a(139) = 1640813492611
a(140) = 3253891093249
a(141) = 58307369350429
a(142) = 16603719439201
a(143) = 104637352579681
a(144) = 717698178620677
a(145) = 20513388000961
a(146) = 95682503446921
a(147) = 2295062283361
a(148) = 22027380041449
a(150) = 659758218778297
a(151) = 538801421393041
a(152) = 407683908691201
a(153) = 3305918887501
a(155) = 10639467691777
a(156) = 24861821169953
a(157) = 3478334679401
a(158) = 141331442532337
a(159) = 15996022879141
a(160) = 1520339048617
a(161) = 2752403727511
a(162) = 191853284858371
a(165) = 60171492397969
a(167) = 10792799203033
a(168) = 116734683934721
a(169) = 53423698848521
a(170) = 6737534294941
a(171) = 3387719303201
a(172) = 108576380939881
a(173) = 28409580180901
a(174) = 22799069430611
a(175) = 3500683748641
a(176) = 36864406699261
a(177) = 218182075691761
a(178) = 275315572388809
a(179) = 9227833267201
a(180) = 292920686606161
a(181) = 17266428629521
a(182) = 272144389369381
a(183) = 473849459816041
a(185) = 225593397919
a(186) = 311136259926097
a(187) = 144504006315841
a(188) = 14685655594249
a(189) = 71855633116801
a(190) = 266804646492061
a(191) = 509907568918441
a(192) = 202970616135841
a(193) = 58278208932721
a(194) = 589249411166989
a(195) = 124445761338001
a(196) = 858329870809321
a(197) = 186373066578841
a(201) = 534919693681
a(202) = 802324538751121
a(203) = 232606449610081
a(206) = 466492208670881
a(207) = 35657087366521
a(208) = 938844932257009
a(209) = 1079942171239
a(210) = 135569332772371
a(214) = 308679446754001
a(216) = 67230098982811
a(217) = 1907431307473
a(218) = 3267961077889
a(219) = 413847154073161
a(220) = 434366327142673
a(221) = 3414146271409
a(223) = 6111751219939
a(224) = 2213587630609
a(225) = 278976258696721
a(226) = 60147974900777
a(227) = 247920676141321
a(228) = 17599414207789
a(230) = 733547013841
a(231) = 119284567146721
a(232) = 271706486418091
a(233) = 166850040563389
a(234) = 5459740740721
a(235) = 684951184963501
a(236) = 471415146233921
a(237) = 435808168218721
a(239) = 63237358424809
a(240) = 67075291742581
a(243) = 326643457502917
a(245) = 30748510093729
a(246) = 113681131017001
a(247) = 472838705571361
a(251) = 86037782768521
a(252) = 226544942470201
a(253) = 295852868300881
a(256) = 347324393184781
a(262) = 88726557903229
a(263) = 182778607585393
a(264) = 902639995598041
a(267) = 84103311076201
a(269) = 137505554397121
a(270) = 185691862389841
a(275) = 30171469191361
a(276) = 58774132848169
a(280) = 46342628597851
a(282) = 19155232884841
a(283) = 20417651396911
a(286) = 59424039230221
a(287) = 346342548087073
a(289) = 335333122310629
a(290) = 92237829955561
a(292) = 22139875582819
a(294) = 3284486673199
a(298) = 5716161256291
a(301) = 174433946530177
a(304) = 583248344253121
a(305) = 913516269610621
a(306) = 362418221500441
a(307) = 431787268056961
a(309) = 22386271857841
a(312) = 68676437370283
a(313) = 516815663303297
a(317) = 46612722630601
a(319) = 387196680013321
a(323) = 15314068130791
a(325) = 64677472557661
a(326) = 56681876172949
a(328) = 97005728268037
a(330) = 112374872517529
a(331) = 183017497463137
a(339) = 179459761020121
a(340) = 251215146358471
a(341) = 78132246215581
a(345) = 93266407023901
a(348) = 647913102541249
a(349) = 10606544136049
a(353) = 559828923440257
a(354) = 142921517891461
a(357) = 668057010350689
a(360) = 245826881776561
a(363) = 208899207727057
a(365) = 987403891009201
a(370) = 122584803003391
a(371) = 509128384975489
a(373) = 361785450237121
a(378) = 256098331149289
a(379) = 272799315674161
a(386) = 195809339861929
a(388) = 81968098956169
a(394) = 975038663971969
a(395) = 25825129162489
a(397) = 723688820413561
a(398) = 491704482753961
a(400) = 5932358886673
a(402) = 81131078472589
a(403) = 768813824846593
a(406) = 65751233028433
a(407) = 957920649572017
a(409) = 19382653622201
a(410) = 466764165410593
a(414) = 50059736866021
a(415) = 892735438510411
a(416) = 303522605836561
a(419) = 551470851860671
a(420) = 193796596629901
a(425) = 105070740188941
a(427) = 582800396617601
a(428) = 70362464581249
a(429) = 186943489269571
a(430) = 639618994408057
a(431) = 567595107954211
a(435) = 150604334361601
a(436) = 782958537406021
a(443) = 92327722290241
a(444) = 186433901916289
a(446) = 331939058141209
a(447) = 78993355796317
a(454) = 507603507510961
a(457) = 181012858733617
a(461) = 127946257707577
a(463) = 24132461746513
a(472) = 403162691222089
a(473) = 541285881574831
a(478) = 121667498301961
a(480) = 398915918374777
a(482) = 959231338715497
a(488) = 10212920220721
a(489) = 230318665188193
a(492) = 398059734553489
a(494) = 457240489374169
a(496) = 671359249176841
a(497) = 867571840268101
a(503) = 541065853026001
a(507) = 7991029901359
a(508) = 434322810357157
a(510) = 501291932351689
a(512) = 961788162899701
a(515) = 108622357428901
a(523) = 778983303926761
a(525) = 167060898315481
a(526) = 589406924955031
a(530) = 324059299005157
a(535) = 439335727769761
a(536) = 48430772527831
a(547) = 117712078117561
a(551) = 918232256400929
a(560) = 487228269407833
a(561) = 35682120672529
a(566) = 630322281662221
a(570) = 238259191994881
a(591) = 751842206115281
a(594) = 217185739973401
a(598) = 69095196855889
a(613) = 298620660945331
a(614) = 66450537040501
a(615) = 959377262271049
a(635) = 279626980287649
a(638) = 527972217183841
a(659) = 363027260785561
a(661) = 202923704101441
a(668) = 806639557689181
a(670) = 583116811950997
a(673) = 911424098937601
a(676) = 30931783745041
a(691) = 469471809590281
a(692) = 235826551730281
a(695) = 927578863585441
a(706) = 449006212584341
a(717) = 761267068528297
a(719) = 38663807592121
a(737) = 225301895806609
a(752) = 44709747732961
a(760) = 251703127095769
a(767) = 603267316619521
a(790) = 117110384184289
a(796) = 54508637981641
a(799) = 71911523404267
a(800) = 177177326318929
a(815) = 70963404421681
a(824) = 681510636081409
a(837) = 180256151763913
a(860) = 570542399253481
a(861) = 214532551137781
a(907) = 629824842551969
a(909) = 102176253760681
a(912) = 86671817900281
a(919) = 62529366058699
a(934) = 510637565929609
a(956) = 257322414362551
a(976) = 141952434183067
a(982) = 601192212565969
a(1015) = 683938014196609
a(1046) = 447619754226769
a(1234) = 684416901956761
a(1260) = 260063696962081
a(1311) = 954918141887569
a(1416) = 276959986009939
a(1452) = 512645597464681
a(1548) = 914209579868729
a(1594) = 700935697920313
a(1596) = 761382476859187