-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlucas-carmichael_multiples_of_lucas-cyclic_numbers.pl
executable file
·856 lines (837 loc) · 26.2 KB
/
lucas-carmichael_multiples_of_lucas-cyclic_numbers.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
#!/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