| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618 |
- #!/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
- # Upper-bounds:
- # a(205) <= 649450807457655279
- # a(271) <= 3394263983671190271
- # a(274) <= 261147917637896799
- # a(303) <= 160372803283722399
- # New term (11 September 2022):
- # a(205) = 10409957634999
- use 5.020;
- use warnings;
- use ntheory qw(:all);
- use experimental qw(signatures);
- my %table = qw(
- 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 3394263983671190271
- 835 2048255
- 839 14800799
- 849 261147917637896799
- 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 160372803283722399
- 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 914506843161999
- 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
- 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 714791836281522999
- 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
- 1627 2452749683
- 1631 202767551
- 1633 76751
- 1637 356628635
- 1639 67199
- 1641 821474220921489687
- 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 430717758620799
- 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 908414916795399
- 1861 10397407
- 1865 4379107655
- 1867 53722314491
- 1871 84062159
- 1873 2170525568639
- 1877 181061935067
- 1879 17664479
- 1883 3722941439
- 1889 10712519
- 1893 570014742966591
- 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
- 1 399 3 399 5 935 7 399 11 935 13 2015 17 935 19 399 21 399 23 4991 29 51359 31 2015 35 8855 37 1584599 39 9486399 41 20705 43 5719 47 18095 53 2915 55 935 57 399 59 46079 61 162687 65 2015 67 22847 71 46079 73 16719263 77 8855 79 12719 83 7055 85 935 89 80189 93 189099039 97 104663 101 20705 103 482143 107 196559 109 60059 111 30073928079 113 90287 115 8855 119 31535 127 162687 129 174550287 131 3441239 133 399 137 13971671 139 155819 143 29315 149 67199 151 390335 155 2015 157 57872555 161 4991 163 208643423 167 196559 173 120581 179 676799 181 90393029 183 162687 185 78402815 187 935 191 73535 193 565861139 197 117215 199 676799 201 487842879 203 51359 205 20705 209 81719 211 760655 215 588455 217 4991 219 6587452767 221 653939 223 2048255 227 776567 229 8164079 233 709019 235 18095 237 9486399 239 6023039 241 3441239 247 6539819 251 63503 253 8855 257 102310415 259 2276351 263 3332999 265 2915 269 653939 271 663679 277 525720239 281 301040639 283 256226219 291 7710848622399 293 3704399 299 7366463 301 5719 305 3354695 307 8699459 309 189099039 311 776567 313 20682759239 317 142842419 319 51359 323 81719 327 11218119879 329 18095 331 196377335 335 150042815 337 427717367 341 22847 347 1811687 349 10138799 353 8046928343 355 265895 359 388079 365 956213495 367 34709759 371 31535 373 192373631 377 2581319 379 1584599 381 162687 383 147455 385 8855 389 11682059 391 81719 397 10749148577 399 399 401 229390847 403 2015 407 2276351 409 261429119 413 1256759 415 7055 417 487842879 419 880319 421 873919799 427 162687 431 10054799 433 14658349 437 81719 439 966239 443 16719263 449 5455799 451 29315 453 37348274919 457 65094623 461 49412285 463 1719119 467 6994259 469 26456759
- );
- sub divceil ($x, $y) { # ceil(x/y)
- my $q = divint($x, $y);
- ($q * $y == $x) ? $q : ($q + 1);
- }
- sub lucas_carmichael_numbers_in_range ($m, $A, $B, $k, $callback) {
- my $L = lcm(map { $_ + 1 } factor($m));
- if ($L == 0) {
- $L = 1;
- }
- $A = vecmax($A, $m, pn_primorial($k));
- if ($A > $B) {
- return;
- }
- sub ($m, $lambda, $p, $k, $u = undef, $v = undef) {
- if ($k == 1) {
- $u //= vecmax($p, divceil($A, $m));
- $v //= divint($B, $m);
- say "# Sieving: $m -> ($u, $v)" if ($v - $u > 1e8);
- if ($v - $u > 1e10) {
- die "Range too large!\n";
- }
- forprimes {
- if ($m % $_ != 0) {
- my $t = $m * $_;
- if (($t + 1) % $lambda == 0 and ($t + 1) % ($_ + 1) == 0) {
- $callback->($t);
- }
- }
- } $u, $v;
- return;
- }
- my $s = rootint(divint($B, $m), $k);
- for (my $r ; $p <= $s ; $p = $r) {
- $r = next_prime($p);
- if ($m % $p == 0) {
- next;
- }
- my $L = lcm($lambda, $p + 1);
- gcd($L, $m) == 1 or next;
- my $t = $m * $p;
- my $u = divceil($A, $t);
- my $v = divint($B, $t);
- if ($u <= $v) {
- __SUB__->($t, $L, $r, $k - 1, (($k == 2 && $r > $u) ? $r : $u), $v);
- }
- }
- }
- ->($m, $L, 3, $k);
- return 1;
- }
- foreach my $m (sort { $a <=>$b } keys %table) {
- #next if ($m < 471);
- #next if ($m <= 633);
- next if ($m <= 849);
- my $upto = $table{$m};
- #$upto = 1e13;
- #next if ($m == 471);
- #next if ($m != 633);
- #$m = 1623;
- #$upto = ~0;
- say "# Searching for m = $m with limit = $upto";
- last if ($upto > ~0);
- my $min = $upto;
- my $found = 0;
- foreach my $k (reverse(1..100)) {
- #foreach my $k (7..100) {
- lucas_carmichael_numbers_in_range($m, 1, $min, $k, sub ($n) { ++$found; if ($n < $min) { $min = $n } });
- }
- if ($m == $upto) {
- $m = $upto;
- $found = 1;
- }
- if (not $found) {
- die "error for m = $m: no term found";
- }
- if ($min < $upto) {
- say "# !!!Smaller term found!!!"
- }
- say "$m $min";
- }
|
