| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857 |
- #!/usr/bin/perl
- # a(n) = least Lucas-Carmichael number which is divisible by b(n), where {b(n)} (A255602) is the list of all numbers which could be a divisor of a Lucas-Carmichael number.
- # https://oeis.org/A253598
- # See also:
- # https://oeis.org/A255602
- # Couldn't find upper-bounds for the following multiples: 2019 2469 2631 2991
- # Upper-bounds > 2^64:
- # 2019: 2172140962024052891965613396799
- # 2469: 390749096137712509119
- # 2631: 1459281990451177943723199
- # 2991: 2613826422645440140263685743399
- use 5.020;
- use strict;
- use warnings;
- use experimental qw(signatures);
- use Storable;
- use Math::GMPz;
- use ntheory qw(:all);
- use Math::Prime::Util::GMP;
- use experimental qw(signatures);
- my @lucas_cyclic = grep {
- my $n = $_;
- vecall { gcd($n, $_ + 1) == 1 } factor($n)
- } grep { is_square_free($_) } grep { $_ > 469 } grep { $_ % 2 == 1 } (1 .. 3000);
- my $lucas_cyclic_lcm = Math::Prime::Util::GMP::lcm(@lucas_cyclic);
- my %table;
- while (<>) {
- next if /^\h*#/;
- /\S/ or next;
- my $n = (split(' ', $_))[-1];
- $n || next;
- $n =~ /^[0-9]+\z/ or next;
- $n < ~0 or next;
- if (Math::Prime::Util::GMP::gcd($n, $lucas_cyclic_lcm) eq '1') {
- next;
- }
- (vecall { ($n + 1) % ($_ + 1) == 0 } factor($n)) || next;
- is_square_free($n) || next;
- foreach my $c (@lucas_cyclic) {
- if ($n % $c == 0) {
- if (not exists $table{$c} or $n < $table{$c}) {
- $table{$c} = $n;
- }
- }
- }
- }
- foreach my $key (sort { $a <=> $b } keys %table) {
- printf("%4d: %25s\n", $key, $table{$key});
- }
- my @unknown;
- foreach my $c (@lucas_cyclic) {
- if (not exists $table{$c}) {
- push @unknown, $c;
- }
- }
- if (@unknown) {
- say "\nCouldn't find upper-bounds for the following multiples: @unknown";
- }
- __END__
- 471: 4131709859199
- 479: 5058719
- 481: 505863371
- 485: 218735
- 487: 1901735
- 489: 532100807679
- 491: 966779
- 493: 10260809
- 497: 194327
- 499: 14970499
- 503: 761039
- 505: 20705
- 509: 11682059
- 511: 50168447
- 515: 760655
- 517: 18095
- 521: 31276151
- 523: 2316562079
- 527: 43383167
- 533: 29315
- 535: 265895
- 541: 4992691535
- 543: 377049487359
- 547: 96078393179
- 551: 60059
- 553: 12719
- 557: 185551739
- 559: 8421335
- 563: 65094623
- 565: 129477095
- 569: 973559
- 571: 25149695
- 577: 5778659039
- 579: 1019982346239
- 583: 2915
- 587: 2416679
- 589: 116628479
- 593: 85595399
- 595: 31535
- 597: 6304359999
- 599: 11141999
- 601: 434886605
- 607: 50561279
- 611: 22575839
- 613: 1645919099
- 617: 1100831039
- 619: 49124459
- 623: 1017359
- 629: 2276351
- 631: 798215
- 633: 10409957634999
- 635: 78402815
- 641: 1172426819
- 643: 178474295
- 647: 3354695
- 649: 46079
- 651: 4962284607
- 653: 5022676835
- 655: 8421335
- 659: 6959699
- 661: 193849487
- 667: 51359
- 669: 3211164543
- 671: 5669279
- 673: 141070895
- 677: 96850943
- 683: 13081499
- 685: 39003215
- 687: 24319371999
- 689: 3700619
- 691: 2710757759
- 697: 120581
- 701: 13287455
- 707: 140096999
- 709: 239110959
- 713: 4991
- 715: 29315
- 719: 3106799
- 721: 760655
- 723: 25603599
- 727: 23287991
- 731: 588455
- 733: 78372051407
- 737: 22847
- 739: 107732159
- 741: 1293531436119
- 743: 1659119
- 749: 265895
- 751: 187498415
- 755: 390335
- 757: 49569379679
- 761: 87562943
- 763: 1566265799
- 767: 1915199
- 769: 6514199
- 773: 11368511
- 777: 1778324753919
- 779: 2150819
- 781: 46079
- 785: 57872555
- 787: 1241099
- 791: 24205391
- 793: 30222023
- 797: 4452839
- 799: 90287
- 803: 16719263
- 805: 8855
- 809: 4587839
- 811: 11195855
- 813: 174550287
- 815: 240080255
- 817: 5719
- 821: 984624479
- 823: 105114383
- 827: 2055095
- 829: 2596088939
- 831: 1651927794936159
- 835: 2048255
- 839: 14800799
- 849: 162023782886679
- 851: 6730559
- 853: 759786719
- 857: 13971671
- 859: 126325399
- 863: 9694079
- 865: 1116663965
- 869: 6023039
- 871: 23176439
- 877: 20271948839
- 881: 6994259
- 883: 603383039
- 887: 501737759
- 889: 162687
- 893: 895679
- 899: 12676799
- 901: 31535
- 903: 2215225217919
- 905: 45708573455
- 907: 285774839
- 911: 10801727
- 913: 20999
- 917: 42624911
- 919: 487842879
- 921: 14970106227
- 923: 7366463
- 929: 33695759
- 935: 935
- 937: 35847939959
- 939: 482519796233727
- 941: 326947004999
- 943: 30071327
- 947: 6613769399
- 949: 306871487
- 953: 7274249
- 955: 73535
- 959: 13971671
- 965: 1840311935
- 967: 4681247
- 971: 796578299
- 977: 22824172799
- 979: 1097459
- 983: 60939119
- 985: 117215
- 989: 588455
- 991: 1218027199
- 993: 1464337823871
- 997: 16070342903
- 1003: 895679
- 1007: 2756159
- 1009: 35669159
- 1011: 69622135643825751
- 1013: 90393029
- 1019: 115372199
- 1021: 142955315
- 1027: 9486399
- 1031: 1759843799
- 1033: 62778871583
- 1037: 3354695
- 1039: 77801359
- 1043: 54958799
- 1047: 286306774599
- 1049: 135479399
- 1051: 135470012351
- 1055: 760655
- 1057: 61947599
- 1061: 1522283543
- 1063: 29407895
- 1067: 218735
- 1069: 12583199
- 1073: 4874639
- 1079: 104663
- 1081: 76751
- 1085: 1747955615
- 1087: 240080255
- 1091: 158453567
- 1093: 888437399
- 1097: 1396023551
- 1099: 2770408655
- 1101: 94637939036799
- 1103: 59668991
- 1105: 49412285
- 1109: 129255059
- 1111: 13670855
- 1115: 2048255
- 1117: 2291560127
- 1119: 2215225217919
- 1121: 88559
- 1123: 96250502879
- 1129: 29343839
- 1133: 1612670279
- 1135: 461819015
- 1137: 37348274919
- 1141: 3075810815
- 1147: 381626399
- 1151: 25194239
- 1153: 15997348079
- 1157: 939989609
- 1159: 1922689439
- 1163: 565861139
- 1165: 9868715
- 1171: 997794304415
- 1177: 196559
- 1181: 3334906619
- 1187: 16923059
- 1189: 2581319
- 1191: 366538619405919
- 1193: 10197581471
- 1201: 572531110799
- 1205: 14605403735
- 1207: 194327
- 1209: 84895311423
- 1211: 1046435999
- 1213: 20373173183
- 1217: 69669599
- 1219: 913031
- 1223: 37425023
- 1227: 187243828239
- 1229: 105818129
- 1231: 295736671
- 1237: 1245426650579
- 1241: 532070063
- 1243: 50407379
- 1247: 113024339
- 1249: 485549999
- 1253: 1256759
- 1255: 11195855
- 1259: 1587599
- 1261: 104663
- 1263: 1707581786703519
- 1265: 8855
- 1271: 34562303
- 1273: 26456759
- 1277: 256226219
- 1279: 62211839
- 1281: 162687
- 1283: 3695056679
- 1285: 102310415
- 1289: 256074029
- 1291: 178474295
- 1295: 461819015
- 1297: 77924443519
- 1299: 12304798623039
- 1301: 49124459
- 1303: 22824172799
- 1307: 1710863
- 1309: 1710863
- 1313: 279173999
- 1315: 67418735
- 1317: 286306774599
- 1319: 3483479
- 1321: 95663965319
- 1327: 193849487
- 1333: 29010079
- 1337: 73535
- 1343: 2193119
- 1349: 9349919
- 1351: 1840311935
- 1355: 240080255
- 1357: 14800799
- 1361: 1925976959
- 1363: 1707839
- 1367: 3741479
- 1371: 12441373101219999
- 1373: 1439402399
- 1379: 117215
- 1381: 221511111527
- 1385: 3075786974315
- 1387: 850615199
- 1389: 99467679
- 1391: 57872555
- 1393: 128912399
- 1397: 54408959
- 1399: 95972799
- 1403: 30222023
- 1405: 900744095
- 1407: 28050394272159
- 1409: 669515939
- 1411: 7055
- 1415: 18209964695
- 1417: 2906220239
- 1423: 239110959
- 1427: 279173999
- 1429: 3032510909
- 1433: 310294655
- 1439: 343979999
- 1443: 30073928079
- 1447: 22695814439
- 1451: 250716839
- 1453: 25578000287
- 1457: 38999519
- 1459: 96403747439
- 1461: 88330062057663
- 1463: 24685199
- 1465: 4609544855
- 1469: 252654779
- 1471: 595462271
- 1477: 760655
- 1481: 1501273409
- 1483: 270696439
- 1487: 73019135
- 1489: 18234757079
- 1493: 45598971599
- 1495: 8421335
- 1497: 306307407999
- 1499: 2249999
- 1501: 88559
- 1505: 588455
- 1507: 11882931599
- 1511: 130225535
- 1513: 80189
- 1517: 7110179
- 1523: 7947283571
- 1529: 10138799
- 1531: 3586258799
- 1533: 6587452767
- 1535: 67418735
- 1537: 35669159
- 1541: 214199
- 1543: 88043680295
- 1549: 890753999
- 1553: 4230625139
- 1555: 2061639215
- 1559: 133763759
- 1565: 9059114946815
- 1567: 130225535
- 1569: 12084948601239
- 1571: 219797039
- 1577: 1241099
- 1579: 14970499
- 1583: 20061359
- 1585: 30036458495
- 1589: 108946607
- 1591: 7110179
- 1597: 119945879
- 1601: 10260809
- 1603: 8164079
- 1607: 31010279
- 1609: 1111321819
- 1613: 208916200349
- 1619: 338340239
- 1621: 143846925641
- 1623: 40576030028823639
- 1627: 2452749683
- 1631: 202767551
- 1633: 76751
- 1637: 356628635
- 1639: 67199
- 1641: 175384415496099
- 1643: 103727519
- 1645: 18095
- 1649: 7234163
- 1651: 32869759
- 1655: 196377335
- 1657: 30222023
- 1659: 108992419599
- 1661: 390335
- 1663: 3259800959
- 1667: 436548959
- 1669: 60301722719
- 1673: 10210319
- 1677: 1464337823871
- 1679: 81802559
- 1685: 288733827095
- 1687: 25603599
- 1691: 1097459
- 1693: 306871487
- 1697: 103264532219
- 1699: 9667141799
- 1703: 3700619
- 1705: 287379455
- 1709: 2924099
- 1711: 152279
- 1713: 17156013520359
- 1721: 2723515199
- 1723: 245754407039
- 1727: 696825503
- 1731: 2250151308831
- 1733: 5778659039
- 1735: 18476015
- 1739: 2276351
- 1741: 315349800479
- 1747: 19318062203
- 1751: 202767551
- 1753: 5083021278719
- 1759: 95972799
- 1763: 7110179
- 1765: 103382437535
- 1767: 189099039
- 1769: 139098239
- 1771: 8855
- 1777: 13228853399
- 1781: 107556371
- 1783: 75173549759
- 1787: 252419111
- 1789: 404717546519
- 1793: 3075810815
- 1799: 275766911
- 1801: 207377944199
- 1803: 53399465726494719
- 1807: 66709019
- 1811: 1834378199
- 1817: 12719
- 1819: 7234163
- 1821: 1778324753919
- 1823: 282639743
- 1829: 12676799
- 1831: 146348770399
- 1835: 15389361455
- 1837: 196559
- 1839: 15187052332978239
- 1841: 325428047
- 1843: 2616973379
- 1847: 1396023551
- 1853: 679389479
- 1855: 31535
- 1857: 620418252540639
- 1861: 10397407
- 1865: 4379107655
- 1867: 53722314491
- 1871: 84062159
- 1873: 2170525568639
- 1877: 181061935067
- 1879: 17664479
- 1883: 3722941439
- 1889: 10712519
- 1893: 227767811184759
- 1897: 108946607
- 1901: 6345558911
- 1903: 19716983
- 1907: 800484227
- 1909: 20999
- 1913: 11097953855
- 1915: 147455
- 1919: 115372199
- 1921: 90287
- 1927: 64456223
- 1929: 290679333699
- 1931: 406647359
- 1933: 726969805631
- 1937: 271038599
- 1939: 987831967199
- 1943: 36981119
- 1949: 1181972999
- 1951: 4962284607
- 1955: 588455
- 1957: 189099039
- 1961: 632648015
- 1963: 1171355471
- 1967: 10346390495
- 1969: 966779
- 1973: 1250201315
- 1979: 97962479
- 1981: 22644087935
- 1983: 128828457866303103
- 1985: 247545314495
- 1987: 1915827647
- 1991: 677913599
- 1993: 43716455
- 1997: 107732159
- 1999: 103949999
- 2003: 8923150679
- 2005: 65766708755
- 2011: 2621128819063
- 2015: 2015
- 2017: 1355053713089
- 2021: 42624911
- 2027: 119213951
- 2029: 3752292599
- 2033: 85595399
- 2035: 1677615335
- 2039: 191341799
- 2041: 57872555
- 2047: 1017359
- 2053: 12494564159
- 2059: 3419999
- 2063: 1205025119
- 2069: 89941499
- 2071: 60059
- 2073: 1082375366719202031
- 2077: 22847
- 2081: 595283349671
- 2083: 17550551879
- 2087: 841029695
- 2089: 8734109
- 2099: 1785201599
- 2101: 73535
- 2105: 53978512895
- 2111: 17835839
- 2113: 332974787039
- 2117: 1106994119
- 2119: 4113065879
- 2123: 1840311935
- 2127: 239110959
- 2129: 213136319
- 2131: 3075810815
- 2135: 36485015
- 2137: 940632662699
- 2141: 110066669
- 2143: 6170539199
- 2153: 9567292559
- 2155: 34818335
- 2159: 54408959
- 2161: 3047828022779
- 2163: 606740995119
- 2165: 4720788995
- 2171: 2581319
- 2173: 3700619
- 2177: 103727519
- 2179: 2075848319
- 2181: 1939478195199
- 2183: 4874639
- 2189: 34347599
- 2191: 151895126159
- 2199: 48590691860026623
- 2201: 966239
- 2203: 371725489511
- 2207: 4200576479
- 2213: 63696779
- 2215: 1569799295
- 2217: 1760703815199
- 2219: 801105599
- 2221: 86753457119
- 2227: 24036011
- 2231: 33413687
- 2233: 51359
- 2237: 72127293479
- 2239: 130401599
- 2243: 347299391
- 2249: 19716983
- 2251: 151007950079
- 2253: 3199214643061359
- 2255: 29315
- 2257: 65644707323
- 2261: 2756159
- 2263: 50168447
- 2267: 1424213279
- 2269: 5619339599
- 2271: 9260716431999
- 2273: 107588615903
- 2279: 146314079
- 2281: 498823548383
- 2285: 499877775935
- 2287: 10467599
- 2289: 1760703815199
- 2291: 6023039
- 2293: 155447718677
- 2297: 1602274663079
- 2305: 49412285
- 2307: 24319371999
- 2309: 16003679
- 2311: 347299391
- 2315: 18476015
- 2317: 196377335
- 2321: 134151479
- 2323: 13670855
- 2327: 12791519
- 2329: 13971671
- 2333: 16337999
- 2335: 483664895
- 2339: 16422119
- 2341: 162927080315
- 2345: 196377335
- 2347: 155232488111
- 2351: 8244564383
- 2357: 20369361347
- 2359: 427717367
- 2361: 2897515809759
- 2363: 212133599
- 2369: 285774839
- 2371: 1760703815199
- 2377: 3975786190079
- 2379: 1293531436119
- 2381: 329681067299
- 2383: 2533760495
- 2387: 121538879
- 2389: 633669327899
- 2393: 131765759
- 2399: 437579999
- 2405: 378984717215
- 2407: 6539819
- 2411: 1273560119
- 2413: 632309759
- 2417: 625343159
- 2419: 16064579
- 2423: 1662161039
- 2429: 1098517679
- 2431: 653939
- 2433: 2513143975698951699
- 2435: 1901735
- 2437: 4200576479
- 2441: 29989401023
- 2447: 1335829535
- 2449: 663679
- 2451: 3063762129999
- 2453: 2048255
- 2455: 1951177535
- 2459: 1119093359
- 2461: 913031
- 2467: 5035238279
- 2471: 38410195103
- 2473: 20173614757295
- 2477: 42968519
- 2479: 1623152519
- 2483: 306871487
- 2485: 265895
- 2487: 9668194735359
- 2489: 69669599
- 2491: 191807
- 2497: 776567
- 2501: 349657307
- 2503: 1303644999
- 2507: 47324639
- 2509: 4338891479
- 2513: 10210319
- 2515: 29407895
- 2519: 8164079
- 2521: 565861139
- 2531: 12156911855
- 2533: 271038599
- 2537: 145235639
- 2539: 68598653759
- 2543: 2380738799
- 2549: 97501799
- 2551: 364571063
- 2555: 2646012669335
- 2557: 215761570079
- 2559: 5419888521900159
- 2561: 187268003
- 2563: 321843599
- 2567: 93277079
- 2569: 34709759
- 2573: 64456223
- 2577: 355739509119
- 2579: 6656399
- 2581: 152279
- 2585: 18095
- 2587: 34347599
- 2591: 564135839
- 2593: 4768791234479
- 2599: 39715319
- 2603: 3796457279
- 2605: 11097953855
- 2609: 156620879
- 2611: 105642493439
- 2613: 45337932436719
- 2615: 683995699295
- 2617: 12489933455
- 2621: 15359508191
- 2623: 551925031679
- 2627: 13715567
- 2629: 6023039
- 2633: 17692009055
- 2635: 206238815
- 2641: 155819
- 2647: 255150939559
- 2649: 4993174719551199
- 2653: 15717335039
- 2657: 17585699864831
- 2659: 827536639
- 2663: 532070063
- 2665: 29315
- 2667: 162687
- 2669: 2117613959
- 2671: 585148280639
- 2677: 681679276199
- 2681: 147455
- 2683: 57612059
- 2687: 50561279
- 2689: 522534307679
- 2693: 117232610471
- 2699: 2834762399
- 2705: 4992691535
- 2707: 238162436591
- 2711: 11756221679
- 2713: 11516618648159
- 2717: 6539819
- 2719: 36981119
- 2721: 15932217695324703807
- 2723: 45343540319
- 2729: 320360039
- 2731: 13646339999
- 2735: 199509500735
- 2737: 194327
- 2741: 182912562755
- 2743: 2766406019
- 2747: 23176439
- 2749: 13872143999
- 2753: 144056231
- 2757: 487842879
- 2759: 126806399
- 2761: 63503
- 2767: 185900609999
- 2771: 3821954399
- 2773: 230159
- 2777: 1670784568739
- 2779: 3262857239663
- 2785: 1778743295
- 2789: 6933149999
- 2791: 3720157305479
- 2795: 8421335
- 2797: 81456412155359
- 2801: 30757890239
- 2803: 318259271519
- 2807: 229390847
- 2811: 9605225627563246239
- 2813: 9572639
- 2815: 856098343295
- 2819: 39750719
- 2827: 845468063
- 2831: 353107799
- 2833: 843018643
- 2837: 24157055
- 2839: 157169879
- 2843: 711526139
- 2847: 4107602292807
- 2849: 2276351
- 2851: 13456893911
- 2855: 25149695
- 2857: 699987190319
- 2861: 5199498431
- 2863: 261429119
- 2867: 139098239
- 2879: 945236159
- 2881: 179310559
- 2885: 87693068735
- 2887: 3568519655
- 2897: 503733257
- 2899: 30071327
- 2901: 72542261956647
- 2903: 3262533647
- 2909: 558705449
- 2911: 34562303
- 2915: 2915
- 2917: 745012846679
- 2921: 71526527
- 2923: 555407999
- 2927: 84674132207
- 2929: 140096999
- 2935: 39003215
- 2939: 561645839
- 2941: 120581
- 2947: 2547918076319
- 2951: 1915199
- 2953: 189667714319
- 2957: 405528169535
- 2959: 653939
- 2963: 79043951
- 2965: 12156224255
- 2969: 26456759
- 2971: 12369233313359
- 2973: 21777264108634719
- 2977: 4955773199
- 2981: 108946607
- 2983: 60712858799
- 2987: 8399793479
- 2993: 3510019799
- 2999: 602801999
- Couldn't find upper-bounds for the following multiples: 2019 2469 2631 2991
|
