Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|ALGOL 68}}
(Add Factor) |
Catskill549 (talk | contribs) |
||
Line 219:
61 241 421
61 3361 4021
</pre>
=={{header|AWK}}==
<lang AWK>
# syntax: GAWK -f CARMICHAEL_3_STRONG_PSEUDOPRIMES.AWK
# converted from C
BEGIN {
printf("%5s%8s%8s%13s\n","P1","P2","P3","PRODUCT")
for (p1=2; p1<62; p1++) {
if (!is_prime(p1)) { continue }
for (h3=1; h3<p1; h3++) {
for (d=1; d<h3+p1; d++) {
if ((h3+p1)*(p1-1)%d == 0 && mod(-p1*p1,h3) == d%h3) {
p2 = int(1+((p1-1)*(h3+p1)/d))
if (!is_prime(p2)) { continue }
p3 = int(1+(p1*p2/h3))
if (!is_prime(p3) || (p2*p3)%(p1-1) != 1) { continue }
printf("%5d x %5d x %5d = %10d\n",p1,p2,p3,p1*p2*p3)
count++
}
}
}
}
printf("%d numbers\n",count)
exit(0)
}
function is_prime(n, i) {
if (n <= 3) {
return(n > 1)
}
else if (!(n%2) || !(n%3)) {
return(0)
}
else {
for (i=5; i*i<=n; i+=6) {
if (!(n%i) || !(n%(i+2))) {
return(0)
}
}
return(1)
}
}
function mod(n,m) {
# the % operator actually calculates the remainder of a / b so we need a small adjustment so it works as expected for negative values
return(((n%m)+m)%m)
}
</lang>
{{out}}
<pre>
P1 P2 P3 PRODUCT
3 x 11 x 17 = 561
5 x 29 x 73 = 10585
5 x 17 x 29 = 2465
5 x 13 x 17 = 1105
7 x 19 x 67 = 8911
7 x 31 x 73 = 15841
7 x 13 x 31 = 2821
7 x 23 x 41 = 6601
7 x 73 x 103 = 52633
7 x 13 x 19 = 1729
13 x 61 x 397 = 314821
13 x 37 x 241 = 115921
13 x 97 x 421 = 530881
13 x 37 x 97 = 46657
13 x 37 x 61 = 29341
17 x 41 x 233 = 162401
17 x 353 x 1201 = 7207201
19 x 43 x 409 = 334153
19 x 199 x 271 = 1024651
23 x 199 x 353 = 1615681
29 x 113 x 1093 = 3581761
29 x 197 x 953 = 5444489
31 x 991 x 15361 = 471905281
31 x 61 x 631 = 1193221
31 x 151 x 1171 = 5481451
31 x 61 x 271 = 512461
31 x 61 x 211 = 399001
31 x 271 x 601 = 5049001
31 x 181 x 331 = 1857241
37 x 109 x 2017 = 8134561
37 x 73 x 541 = 1461241
37 x 613 x 1621 = 36765901
37 x 73 x 181 = 488881
37 x 73 x 109 = 294409
41 x 1721 x 35281 = 2489462641
41 x 881 x 12041 = 434932961
41 x 101 x 461 = 1909001
41 x 241 x 761 = 7519441
41 x 241 x 521 = 5148001
41 x 73 x 137 = 410041
41 x 61 x 101 = 252601
43 x 631 x 13567 = 368113411
43 x 271 x 5827 = 67902031
43 x 127 x 2731 = 14913991
43 x 127 x 1093 = 5968873
43 x 211 x 757 = 6868261
43 x 631 x 1597 = 43331401
43 x 127 x 211 = 1152271
43 x 211 x 337 = 3057601
43 x 433 x 643 = 11972017
43 x 547 x 673 = 15829633
43 x 3361 x 3907 = 564651361
47 x 3359 x 6073 = 958762729
47 x 1151 x 1933 = 104569501
47 x 3727 x 5153 = 902645857
53 x 157 x 2081 = 17316001
53 x 79 x 599 = 2508013
53 x 157 x 521 = 4335241
59 x 1451 x 2089 = 178837201
61 x 421 x 12841 = 329769721
61 x 181 x 5521 = 60957361
61 x 1301 x 19841 = 1574601601
61 x 277 x 2113 = 35703361
61 x 181 x 1381 = 15247621
61 x 541 x 3001 = 99036001
61 x 661 x 2521 = 101649241
61 x 271 x 571 = 9439201
61 x 241 x 421 = 6189121
61 x 3361 x 4021 = 824389441
69 numbers
</pre>
| |||