Carmichael 3 strong pseudoprimes
An almost direct translation of the pseudocode. We take the liberty of going up to 67 to show we aren't limited to 32-bit integers. (Raku uses arbitrary precision in any case.)
for (2..67).grep: *.is-prime -> \Prime1 {
for 1 ^..^ Prime1 -> \h3 {
my \g = h3 + Prime1;
for 0 ^..^ h3 + Prime1 -> \d {
if (h3 + Prime1) * (Prime1 - 1) %% d and -Prime1**2 % h3 == d % h3 {
my \Prime2 = floor 1 + (Prime1 - 1) * g / d;
next unless Prime2.is-prime;
my \Prime3 = floor 1 + Prime1 * Prime2 / h3;
next unless Prime3.is-prime;
next unless (Prime2 * Prime3) % (Prime1 - 1) == 1;
say "{Prime1} × {Prime2} × {Prime3} == {Prime1 * Prime2 * Prime3}";
}
}
}
}
Output:
3 × 11 × 17 == 561
5 × 29 × 73 == 10585
5 × 17 × 29 == 2465
5 × 13 × 17 == 1105
7 × 19 × 67 == 8911
7 × 31 × 73 == 15841
7 × 13 × 31 == 2821
7 × 23 × 41 == 6601
7 × 73 × 103 == 52633
7 × 13 × 19 == 1729
13 × 61 × 397 == 314821
13 × 37 × 241 == 115921
13 × 97 × 421 == 530881
13 × 37 × 97 == 46657
13 × 37 × 61 == 29341
17 × 41 × 233 == 162401
17 × 353 × 1201 == 7207201
19 × 43 × 409 == 334153
19 × 199 × 271 == 1024651
23 × 199 × 353 == 1615681
29 × 113 × 1093 == 3581761
29 × 197 × 953 == 5444489
31 × 991 × 15361 == 471905281
31 × 61 × 631 == 1193221
31 × 151 × 1171 == 5481451
31 × 61 × 271 == 512461
31 × 61 × 211 == 399001
31 × 271 × 601 == 5049001
31 × 181 × 331 == 1857241
37 × 109 × 2017 == 8134561
37 × 73 × 541 == 1461241
37 × 613 × 1621 == 36765901
37 × 73 × 181 == 488881
37 × 73 × 109 == 294409
41 × 1721 × 35281 == 2489462641
41 × 881 × 12041 == 434932961
41 × 101 × 461 == 1909001
41 × 241 × 761 == 7519441
41 × 241 × 521 == 5148001
41 × 73 × 137 == 410041
41 × 61 × 101 == 252601
43 × 631 × 13567 == 368113411
43 × 271 × 5827 == 67902031
43 × 127 × 2731 == 14913991
43 × 127 × 1093 == 5968873
43 × 211 × 757 == 6868261
43 × 631 × 1597 == 43331401
43 × 127 × 211 == 1152271
43 × 211 × 337 == 3057601
43 × 433 × 643 == 11972017
43 × 547 × 673 == 15829633
43 × 3361 × 3907 == 564651361
47 × 3359 × 6073 == 958762729
47 × 1151 × 1933 == 104569501
47 × 3727 × 5153 == 902645857
53 × 157 × 2081 == 17316001
53 × 79 × 599 == 2508013
53 × 157 × 521 == 4335241
59 × 1451 × 2089 == 178837201
61 × 421 × 12841 == 329769721
61 × 181 × 5521 == 60957361
61 × 1301 × 19841 == 1574601601
61 × 277 × 2113 == 35703361
61 × 181 × 1381 == 15247621
61 × 541 × 3001 == 99036001
61 × 661 × 2521 == 101649241
61 × 271 × 571 == 9439201
61 × 241 × 421 == 6189121
61 × 3361 × 4021 == 824389441
67 × 2311 × 51613 == 7991602081
67 × 331 × 7393 == 163954561
67 × 331 × 463 == 10267951
Last updated