123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437 |
- #!/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
|