Rosetta Code

Carmichael 3 strong pseudoprimes: Difference between revisions

Page Discussion

Carmichael 3 strong pseudoprimes (view source)

Revision as of 09:19, 13 November 2023

48,706 bytes added ,  7 months ago
m
→‎{{header|RPL}}: tweaked the code
m (→‎{{header|REXX}}: changed code (both programs) to support a comma for omission of a value.)
m (→‎{{header|RPL}}: tweaked the code)
 
(78 intermediate revisions by 31 users not shown)
Line 1:
{{task|Prime Numbers}}
 
A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it.
Line 8:
 
 
;Task:
Find Carmichael numbers of the form:
:::: <mathbig> Prime_1<i>Prime</i><sub>1</sub> \&times; Prime_2<i>Prime</i><sub>2</sub> \&times Prime_3; <i>Prime</mathi><sub>3</sub> </big>
 
where &nbsp; <big> (<mathi>Prime</i><sub>1</sub> Prime_1 < Prime_2 <i>Prime</i><sub>2</sub> Prime_3 < <i>Prime</i><sub>3</mathsub>) </big> &nbsp; for all &nbsp; <mathbig> Prime_1<i>Prime</i><sub>1</sub> </mathbig> &nbsp; up to &nbsp; '''61'''.
<br>(See page 7 of &nbsp; [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] &nbsp; for solutions.)
 
 
;Pseudocode:
For a given &nbsp; <math> Prime_1 </math>
 
<tt>for 1 < h3 < Prime<sub>1</sub></tt>
: <tt>for 0 < d < h3+Prime<sub>1</sub></tt>
:: <tt>if (h3+Prime<sub>1</sub>)*(Prime<sub>1</sub>-1) mod d == 0 and -Prime<sub>1</sub> squared mod h3 == d mod h3</tt>
:: <tt>then</tt>
::: <tt>Prime<sub>2</sub> = 1 + ((Prime<sub>1</sub>-1) * (h3+Prime<sub>1</sub>)/d)</tt>
::: <tt>next d if Prime<sub>2</sub> is not prime</tt>
::: <tt>Prime<sub>3</sub> = 1 + (Prime<sub>1</sub>*Prime<sub>2</sub>/h3)</tt>
::: <tt>next d if Prime<sub>3</sub> is not prime</tt>
::: <tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt>
::: <tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt>
<br><br>
;related task
 
[[Chernick's Carmichael numbers]]
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">F mod_(n, m)
R ((n % m) + m) % m
F is_prime(n)
I n C (2, 3)
R 1B
E I n < 2 | n % 2 == 0 | n % 3 == 0
R 0B
V div = 5
V inc = 2
L div ^ 2 <= n
I n % div == 0
R 0B
div += inc
inc = 6 - inc
R 1B
L(p) 2 .< 62
I !is_prime(p)
L.continue
L(h3) 2 .< p
V g = h3 + p
L(d) 1 .< g
I (g * (p - 1)) % d != 0 | mod_(-p * p, h3) != d % h3
L.continue;
V q = 1 + (p - 1) * g I/ d;
I !is_prime(q)
L.continue
V r = 1 + (p * q I/ h3)
I !is_prime(r) | (q * r) % (p - 1) != 1
L.continue
print(p‘ x ’q‘ x ’r)</syntaxhighlight>
{{out}}
<pre>
3 x 11 x 17
5 x 29 x 73
5 x 17 x 29
5 x 13 x 17
7 x 19 x 67
7 x 31 x 73
7 x 13 x 31
7 x 23 x 41
...
61 x 1301 x 19841
61 x 277 x 2113
61 x 181 x 1381
61 x 541 x 3001
61 x 661 x 2521
61 x 271 x 571
61 x 241 x 421
61 x 3361 x 4021
</pre>
=={{header|Ada}}==
 
Uses the Miller_Rabin package from
[[Miller-Rabin primality test#ordinary integers]].
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO, Miller_Rabin;
 
procedure Nemesis is
Line 75 ⟶ 131:
end if;
end loop;
end Nemesis;</langsyntaxhighlight>
 
{{out}}
Line 89 ⟶ 145:
61 * 241 * 421 = 6189121
61 * 3361 * 4021 = 824389441</pre>
=={{header|ALGOL 68}}==
Uses the Sieve of Eratosthenes code from the Smith Numbers task with an increased upper-bound (included here for convenience).
<syntaxhighlight lang="algol68"># sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise #
PROC sieve = ( REF[]BOOL s )VOID:
BEGIN
# start with everything flagged as prime #
FOR i TO UPB s DO s[ i ] := TRUE OD;
# sieve out the non-primes #
s[ 1 ] := FALSE;
FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO
IF s[ i ] THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := FALSE OD FI
OD
END # sieve # ;
 
# construct a sieve of primes up to the maximum number required for the task #
# For Prime1, we need to check numbers up to around 120 000 #
INT max number = 200 000;
[ 1 : max number ]BOOL is prime;
sieve( is prime );
 
# Find the Carmichael 3 Stromg Pseudoprimes for Prime1 up to 61 #
 
FOR prime1 FROM 2 TO 61 DO
IF is prime[ prime 1 ] THEN
FOR h3 TO prime1 - 1 DO
FOR d TO ( h3 + prime1 ) - 1 DO
IF ( h3 + prime1 ) * ( prime1 - 1 ) MOD d = 0
AND ( - ( prime1 * prime1 ) ) MOD h3 = d MOD h3
THEN
INT prime2 = 1 + ( ( prime1 - 1 ) * ( h3 + prime1 ) OVER d );
IF is prime[ prime2 ] THEN
INT prime3 = 1 + ( prime1 * prime2 OVER h3 );
IF is prime[ prime3 ] THEN
IF ( prime2 * prime3 ) MOD ( prime1 - 1 ) = 1 THEN
print( ( whole( prime1, 0 ), " ", whole( prime2, 0 ), " ", whole( prime3, 0 ) ) );
print( ( newline ) )
FI
FI
FI
FI
OD
OD
FI
OD</syntaxhighlight>
{{out}}
<pre>
3 11 17
5 29 73
5 17 29
5 13 17
7 19 67
7 31 73
7 13 31
7 23 41
7 73 103
7 13 19
13 61 397
13 37 241
13 97 421
13 37 97
13 37 61
...
59 1451 2089
61 421 12841
61 181 5521
61 1301 19841
61 277 2113
61 181 1381
61 541 3001
61 661 2521
61 271 571
61 241 421
61 3361 4021
</pre>
 
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">printOneLine: function [a,b,c,d]->
print [
pad to :string a 3 "x"
pad to :string b 5 "x"
pad to :string c 5 "="
pad to :string d 10
]
 
2..61 | select => prime?
| loop 'p ->
loop 2..p 'h3 [
g: h3 + p
loop 1..g 'd ->
if and? -> zero? mod g*p-1 d
-> zero? mod d+p*p h3 [
 
q: 1 + ((p-1)*g)/d
 
if prime? q [
r: 1 + (p * q) / h3
 
if and? [prime? r]
[one? (q*r) % p-1]->
printOneLine p q r (p*q*r)
]
]
]</syntaxhighlight>
 
{{out}}
 
<pre> 3 x 11 x 17 = 561
3 x 3 x 5 = 45
5 x 29 x 73 = 10585
5 x 5 x 13 = 325
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 7 x 13 = 637
7 x 73 x 103 = 52633
7 x 13 x 19 = 1729
11 x 11 x 61 = 7381
11 x 11 x 41 = 4961
11 x 11 x 31 = 3751
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 17 x 97 = 28033
17 x 353 x 1201 = 7207201
19 x 43 x 409 = 334153
19 x 19 x 181 = 65341
19 x 19 x 73 = 26353
19 x 19 x 37 = 13357
19 x 199 x 271 = 1024651
23 x 23 x 89 = 47081
23 x 23 x 67 = 35443
23 x 199 x 353 = 1615681
29 x 29 x 421 = 354061
29 x 113 x 1093 = 3581761
29 x 29 x 281 = 236321
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 31 x 241 = 231601
31 x 61 x 271 = 512461
31 x 61 x 211 = 399001
31 x 271 x 601 = 5049001
31 x 31 x 61 = 58621
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 37 x 73 = 99937
37 x 73 x 109 = 294409
41 x 1721 x 35281 = 2489462641
41 x 881 x 12041 = 434932961
41 x 41 x 281 = 472361
41 x 41 x 241 = 405121
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 43 x 463 = 856087
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 47 x 277 = 611893
47 x 47 x 139 = 307051
47 x 3359 x 6073 = 958762729
47 x 1151 x 1933 = 104569501
47 x 3727 x 5153 = 902645857
53 x 53 x 937 = 2632033
53 x 157 x 2081 = 17316001
53 x 79 x 599 = 2508013
53 x 53 x 313 = 879217
53 x 157 x 521 = 4335241
53 x 53 x 157 = 441013
59 x 59 x 1741 = 6060421
59 x 59 x 349 = 1214869
59 x 59 x 233 = 811073
59 x 1451 x 2089 = 178837201
61 x 421 x 12841 = 329769721
61 x 181 x 5521 = 60957361
61 x 61 x 1861 = 6924781
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</pre>
 
=={{header|AWK}}==
<syntaxhighlight 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)
}
</syntaxhighlight>
{{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>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">for i = 3 to max_sieve step 2
isprime[i] = 1
next i
 
isprime[2] = 1
for i = 3 to sqr(max_sieve) step 2
if isprime[i] = 1 then
for j = i * i to max_sieve step i * 2
isprime[j] = 0
next j
end if
next i
 
subroutine carmichael3(p1)
if isprime[p1] <> 0 then
for h3 = 1 to p1 -1
t1 = (h3 + p1) * (p1 -1)
t2 = (-p1 * p1) % h3
if t2 < 0 then t2 = t2 + h3
for d = 1 to h3 + p1 -1
if t1 % d = 0 and t2 = (d % h3) then
p2 = 1 + (t1 \ d)
if isprime[p2] = 0 then continue for
p3 = 1 + (p1 * p2 \ h3)
if isprime[p3] = 0 or ((p2 * p3) % (p1 -1)) <> 1 then continue for
print p1; " * "; p2; " * "; p3
end if
next d
next h3
end if
end subroutine
 
for i = 2 to 61
call carmichael3(i)
next i
end</syntaxhighlight>
 
==={{header|Chipmunk Basic}}===
{{trans|FreeBASIC}}
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="vbnet">100 cls
110 max_sieve = 10000000 ' 10^7
120 dim isprime(max_sieve)
130 sub carmichael3(p1)
140 if isprime(p1) = 0 then goto 440
150 for h3 = 1 to p1-1
160 t1 = (h3+p1)*(p1-1)
170 t2 = (-p1*p1) mod h3
180 if t2 < 0 then t2 = t2+h3
190 for d = 1 to h3+p1-1
200 if t1 mod d = 0 and t2 = (d mod h3) then
210 p2 = 1+int(t1/d)
220 if isprime(p2) = 0 then goto 270
230 p3 = 1+int(p1*p2/h3)
240 if isprime(p3) = 0 or ((p2*p3) mod (p1-1)) <> 1 then goto 270
250 print format$(p1,"###");" * ";format$(p2,"####");" * ";format$(p3,"#####")
260 endif
270 next d
280 next h3
290 end sub
300 'set up sieve
310 for i = 3 to max_sieve step 2
320 isprime(i) = 1
330 next i
340 isprime(2) = 1
350 for i = 3 to sqr(max_sieve) step 2
360 if isprime(i) = 1 then
370 for j = i*i to max_sieve step i*2
380 isprime(j) = 0
390 next j
400 endif
410 next i
420 for i = 2 to 61
430 carmichael3(i)
440 next i
450 end</syntaxhighlight>
 
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' version 17-10-2016
' compile with: fbc -s console
 
' using a sieve for finding primes
 
#Define max_sieve 10000000 ' 10^7
ReDim Shared As Byte isprime(max_sieve)
 
' translated the pseudo code to FreeBASIC
Sub carmichael3(p1 As Integer)
 
If isprime(p1) = 0 Then Exit Sub
 
Dim As Integer h3, d, p2, p3, t1, t2
 
For h3 = 1 To p1 -1
t1 = (h3 + p1) * (p1 -1)
t2 = (-p1 * p1) Mod h3
If t2 < 0 Then t2 = t2 + h3
For d = 1 To h3 + p1 -1
If t1 Mod d = 0 And t2 = (d Mod h3) Then
p2 = 1 + (t1 \ d)
If isprime(p2) = 0 Then Continue For
p3 = 1 + (p1 * p2 \ h3)
If isprime(p3) = 0 Or ((p2 * p3) Mod (p1 -1)) <> 1 Then Continue For
Print Using "### * #### * #####"; p1; p2; p3
End If
Next d
Next h3
End Sub
 
' ------=< MAIN >=------
 
Dim As UInteger i, j
 
'set up sieve
For i = 3 To max_sieve Step 2
isprime(i) = 1
Next i
 
isprime(2) = 1
For i = 3 To Sqr(max_sieve) Step 2
If isprime(i) = 1 Then
For j = i * i To max_sieve Step i * 2
isprime(j) = 0
Next j
End If
Next i
 
For i = 2 To 61
carmichael3(i)
Next i
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre> 3 * 11 * 17
5 * 29 * 73
5 * 17 * 29
5 * 13 * 17
7 * 19 * 67
7 * 31 * 73
7 * 13 * 31
7 * 23 * 41
7 * 73 * 103
7 * 13 * 19
13 * 61 * 397
13 * 37 * 241
13 * 97 * 421
13 * 37 * 97
13 * 37 * 61
17 * 41 * 233
17 * 353 * 1201
19 * 43 * 409
19 * 199 * 271
23 * 199 * 353
29 * 113 * 1093
29 * 197 * 953
31 * 991 * 15361
31 * 61 * 631
31 * 151 * 1171
31 * 61 * 271
31 * 61 * 211
31 * 271 * 601
31 * 181 * 331
37 * 109 * 2017
37 * 73 * 541
37 * 613 * 1621
37 * 73 * 181
37 * 73 * 109
41 * 1721 * 35281
41 * 881 * 12041
41 * 101 * 461
41 * 241 * 761
41 * 241 * 521
41 * 73 * 137
41 * 61 * 101
43 * 631 * 13567
43 * 271 * 5827
43 * 127 * 2731
43 * 127 * 1093
43 * 211 * 757
43 * 631 * 1597
43 * 127 * 211
43 * 211 * 337
43 * 433 * 643
43 * 547 * 673
43 * 3361 * 3907
47 * 3359 * 6073
47 * 1151 * 1933
47 * 3727 * 5153
53 * 157 * 2081
53 * 79 * 599
53 * 157 * 521
59 * 1451 * 2089
61 * 421 * 12841
61 * 181 * 5521
61 * 1301 * 19841
61 * 277 * 2113
61 * 181 * 1381
61 * 541 * 3001
61 * 661 * 2521
61 * 271 * 571
61 * 241 * 421
61 * 3361 * 4021</pre>
 
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public isprime[1000000] As Integer
 
Public Sub Main()
Dim max_sieve As Integer = 1000000
Dim i As Integer, j As Integer
'set up sieve
For i = 3 To max_sieve Step 2
isprime[i] = 1
Next
isprime[2] = 1
For i = 3 To Sqr(max_sieve) Step 2
If isprime[i] = 1 Then
For j = i * i To max_sieve Step i * 2
isprime[j] = 0
Next
End If
Next
For i = 2 To 61
If isprime[i] <> 0 Then carmichael3(i)
Next
End
 
Sub carmichael3(p1 As Integer)
Dim h3 As Integer, d As Integer
Dim p2 As Integer, p3 As Integer, t1 As Integer, t2 As Integer
For h3 = 1 To p1 - 1
t1 = (h3 + p1) * (p1 - 1)
t2 = (-p1 * p1) Mod h3
If t2 < 0 Then t2 = t2 + h3
For d = 1 To h3 + p1 - 1
If t1 Mod d = 0 And t2 = (d Mod h3) Then
p2 = 1 + (t1 \ d)
If isprime[p2] = 0 Then Continue
p3 = 1 + ((p1 * p2) \ h3)
If isprime[p3] = 0 Or ((p2 * p3) Mod (p1 - 1)) <> 1 Then Continue
Print Format$(p1, "###"); " * "; Format$(p2, "####"); " * "; Format$(p3, "#####")
End If
Next
Next
End Sub</syntaxhighlight>
 
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">max_sieve = 1e7
dim isprime(max_sieve)
 
//set up sieve
for i = 3 to max_sieve step 2
isprime(i) = 1
next i
 
isprime(2) = 1
for i = 3 to sqrt(max_sieve) step 2
if isprime(i) = 1 then
for j = i * i to max_sieve step i * 2
isprime(j) = 0
next j
fi
next i
 
for i = 2 to 61
carmichael3(i)
next i
end
sub carmichael3(p1)
local h3, d, p2, p3, t1, t2
 
if isprime(p1) = 0 return
for h3 = 1 to p1 -1
t1 = (h3 + p1) * (p1 -1)
t2 = mod((-p1 * p1), h3)
if t2 < 0 t2 = t2 + h3
for d = 1 to h3 + p1 -1
if mod(t1, d) = 0 and t2 = mod(d, h3) then
p2 = 1 + int(t1 / d)
if isprime(p2) = 0 continue
p3 = 1 + int(p1 * p2 / h3)
if isprime(p3) = 0 or mod((p2 * p3), (p1 -1)) <> 1 continue
print p1 using ("###"), " * ", p2 using ("####"), " * ", p3 using ("#####")
fi
next d
next h3
end sub</syntaxhighlight>
 
==={{header|ZX Spectrum Basic}}===
{{trans|C}}
<syntaxhighlight lang="zxbasic">10 FOR p=2 TO 61
20 LET n=p: GO SUB 1000
30 IF NOT n THEN GO TO 200
40 FOR h=1 TO p-1
50 FOR d=1 TO h-1+p
60 IF NOT (FN m((h+p)*(p-1),d)=0 AND FN w(-p*p,h)=FN m(d,h)) THEN GO TO 180
70 LET q=INT (1+((p-1)*(h+p)/d))
80 LET n=q: GO SUB 1000
90 IF NOT n THEN GO TO 180
100 LET r=INT (1+(p*q/h))
110 LET n=r: GO SUB 1000
120 IF (NOT n) OR ((FN m((q*r),(p-1))<>1)) THEN GO TO 180
130 PRINT p;" ";q;" ";r
180 NEXT d
190 NEXT h
200 NEXT p
210 STOP
1000 IF n<4 THEN LET n=(n>1): RETURN
1010 IF (NOT FN m(n,2)) OR (NOT FN m(n,3)) THEN LET n=0: RETURN
1020 LET i=5
1030 IF NOT ((i*i)<=n) THEN LET n=1: RETURN
1040 IF (NOT FN m(n,i)) OR NOT FN m(n,(i+2)) THEN LET n=0: RETURN
1050 LET i=i+6
1060 GO TO 1030
2000 DEF FN m(a,b)=a-(INT (a/b)*b): REM Mod function
2010 DEF FN w(a,b)=FN m(FN m(a,b)+b,b): REM Mod function modified
</syntaxhighlight>
 
=={{header|C}}==
<syntaxhighlight lang="c">
<lang C>
#include <stdio.h>
 
Line 140 ⟶ 855:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 159 ⟶ 874:
61 3361 4021
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
 
int mod(int n, int d) {
return (d + n % d) % d;
}
 
bool is_prime(int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
 
void print_carmichael_numbers(int prime1) {
for (int h3 = 1; h3 < prime1; ++h3) {
for (int d = 1; d < h3 + prime1; ++d) {
if (mod((h3 + prime1) * (prime1 - 1), d) != 0
|| mod(-prime1 * prime1, h3) != mod(d, h3))
continue;
int prime2 = 1 + (prime1 - 1) * (h3 + prime1)/d;
if (!is_prime(prime2))
continue;
int prime3 = 1 + prime1 * prime2/h3;
if (!is_prime(prime3))
continue;
if (mod(prime2 * prime3, prime1 - 1) != 1)
continue;
unsigned int c = prime1 * prime2 * prime3;
std::cout << std::setw(2) << prime1 << " x "
<< std::setw(4) << prime2 << " x "
<< std::setw(5) << prime3 << " = "
<< std::setw(10) << c << '\n';
}
}
}
 
int main() {
for (int p = 2; p <= 61; ++p) {
if (is_prime(p))
print_carmichael_numbers(p);
}
return 0;
}</syntaxhighlight>
 
{{out}}
<pre style="height:50ex">
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
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="lisp">
(ns example
(:gen-class))
 
(defn prime? [n]
" Prime number test (using Java) "
(.isProbablePrime (biginteger n) 16))
 
(defn carmichael [p1]
" Triplets of Carmichael primes, with first element prime p1 "
(if (prime? p1)
(into [] (for [h3 (range 2 p1)
:let [g (+ h3 p1)]
d (range 1 g)
:when (and (= (mod (* g (dec p1)) d) 0)
(= (mod (- (* p1 p1)) h3) (mod d h3)))
:let [p2 (inc (quot (* (dec p1) g) d))]
:when (prime? p2)
:let [p3 (inc (quot (* p1 p2) h3))]
:when (prime? p3)
:when (= (mod (* p2 p3) (dec p1)) 1)]
[p1 p2 p3]))))
 
; Generate Result
(def numbers (mapcat carmichael (range 2 62)))
(println (count numbers) "Carmichael numbers found:")
(doseq [t numbers]
(println (format "%5d x %5d x %5d = %10d" (first t) (second t) (last t) (apply * t))))
</syntaxhighlight>
{{Out}}
<pre>
69 Carmichael numbers found
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
 
</pre>
=={{header|D}}==
<langsyntaxhighlight lang="d">enum mod = (in int n, in int m) pure nothrow @nogc=> ((n % m) + m) % m;
 
bool isPrime(in uint n) pure nothrow @nogc {
Line 193 ⟶ 1,139:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>3 x 11 x 17
Line 264 ⟶ 1,210:
61 x 241 x 421
61 x 3361 x 4021</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc carmichael3 p1 . .
for h3 = 1 to p1 - 1
for d = 1 to h3 + p1 - 1
if (h3 + p1) * (p1 - 1) mod d = 0 and -p1 * p1 mod h3 = d mod h3
p2 = 1 + (p1 - 1) * (h3 + p1) div d
if isprim p2 = 1
p3 = 1 + (p1 * p2 div h3)
if isprim p3 = 1 and (p2 * p3) mod (p1 - 1) = 1
print p1 & " " & p2 & " " & p3
.
.
.
.
.
.
for p1 = 2 to 61
if isprim p1 = 1
carmichael3 p1
.
.
</syntaxhighlight>
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
;; charmichaël numbers up to N-th prime ; 61 is 18-th prime
(define (charms (N 18) local: (h31 0) (Prime2 0) (Prime3 0))
Line 281 ⟶ 1,261:
#:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1)))
(printf " 💥 %12d = %d x %d x %d" (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))
</syntaxhighlight>
</lang>
{{out}}
<langsyntaxhighlight lang="scheme">
(charms 3)
💥 561 = 3 x 11 x 17
Line 306 ⟶ 1,286:
💥 6189121 = 61 x 241 x 421
💥 824389441 = 61 x 3361 x 4021
</syntaxhighlight>
</lang>
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Carmichael Number . Nigel Galloway: November 19th., 2017
let fN n = Seq.collect ((fun g->(Seq.map(fun e->(n,1+(n-1)*(n+g)/e,g,e))){1..(n+g-1)})){2..(n-1)}
let fG (P1,P2,h3,d) =
let mod' n g = (n%g+g)%g
let fN P3 = if isPrime P3 && (P2*P3)%(P1-1)=1 then Some (P1,P2,P3) else None
if isPrime P2 && ((h3+P1)*(P1-1))%d=0 && mod' (-P1*P1) h3=d%h3 then fN (1+P1*P2/h3) else None
let carms g = primes|>Seq.takeWhile(fun n->n<=g)|>Seq.collect fN|>Seq.choose fG
carms 61 |> Seq.iter (fun (P1,P2,P3)->printfn "%2d x %4d x %5d = %10d" P1 P2 P3 ((uint64 P3)*(uint64 (P1*P2))))
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Factor}}==
Note the use of <code>rem</code> instead of <code>mod</code> when the remainder should always be positive.
<syntaxhighlight lang="factor">USING: formatting kernel locals math math.primes math.ranges
sequences ;
IN: rosetta-code.carmichael
 
:: carmichael ( p1 -- )
1 p1 (a,b) [| h3 |
h3 p1 + [1,b) [| d |
h3 p1 + p1 1 - * d mod zero?
p1 neg p1 * h3 rem d h3 mod = and
[
p1 1 - h3 p1 + * d /i 1 + :> p2
p1 p2 * h3 /i 1 + :> p3
p2 p3 [ prime? ] both?
p2 p3 * p1 1 - mod 1 = and
[ p1 p2 p3 "%d %d %d\n" printf ] when
] when
] each
] each
;
 
: carmichael-demo ( -- ) 61 primes-upto [ carmichael ] each ;
 
MAIN: carmichael-demo</syntaxhighlight>
{{out}}
<pre>
3 11 17
5 29 73
5 17 29
5 13 17
7 19 67
7 31 73
7 13 31
7 23 41
7 73 103
7 13 19
13 61 397
13 37 241
13 97 421
13 37 97
13 37 61
17 41 233
17 353 1201
19 43 409
19 199 271
23 199 353
29 113 1093
29 197 953
31 991 15361
31 61 631
31 151 1171
31 61 271
31 61 211
31 271 601
31 181 331
37 109 2017
37 73 541
37 613 1621
37 73 181
37 73 109
41 1721 35281
41 881 12041
41 101 461
41 241 761
41 241 521
41 73 137
41 61 101
43 631 13567
43 271 5827
43 127 2731
43 127 1093
43 211 757
43 631 1597
43 127 211
43 211 337
43 433 643
43 547 673
43 3361 3907
47 3359 6073
47 1151 1933
47 3727 5153
53 157 2081
53 79 599
53 157 521
59 1451 2089
61 421 12841
61 181 5521
61 1301 19841
61 277 2113
61 181 1381
61 541 3001
61 661 2521
61 271 571
61 241 421
61 3361 4021
</pre>
=={{header|Fortran}}==
===Plan===
This is F77 style, and directly translates the given calculation as per ''formula translation''. It turns out that the normal integers suffice for the demonstration, except for just one of the products of the three primes: 41x1721x35281 = 2489462641, which is bigger than 2147483647, the 32-bit limit. Fortunately, INTEGER*8 variables are also available, so the extension is easy. Otherwise, one would have to mess about with using two integers in a bignum style, one holding say the millions, and the second the number up to a million.
===Source===
So, using the double MOD approach (see the ''Discussion'') - which gives the same result for either style of MOD... <syntaxhighlight lang="fortran"> LOGICAL FUNCTION ISPRIME(N) !Ad-hoc, since N is not going to be big...
INTEGER N !Despite this intimidating allowance of 32 bits...
INTEGER F !A possible factor.
ISPRIME = .FALSE. !Most numbers aren't prime.
DO F = 2,SQRT(DFLOAT(N)) !Wince...
IF (MOD(N,F).EQ.0) RETURN !Not even avoiding even numbers beyond two.
END DO !Nice and brief, though.
ISPRIME = .TRUE. !No factor found.
END FUNCTION ISPRIME !So, done. Hopefully, not often.
 
PROGRAM CHASE
INTEGER P1,P2,P3 !The three primes to be tested.
INTEGER H3,D !Assistants.
INTEGER MSG !File unit number.
MSG = 6 !Standard output.
WRITE (MSG,1) !A heading would be good.
1 FORMAT ("Carmichael numbers that are the product of three primes:"
& /" P1 x P2 x P3 =",9X,"C")
DO P1 = 2,61 !Step through the specified range.
IF (ISPRIME(P1)) THEN !Selecting only the primes.
DO H3 = 2,P1 - 1 !For 1 < H3 < P1.
DO D = 1,H3 + P1 - 1 !For 0 < D < H3 + P1.
IF (MOD((H3 + P1)*(P1 - 1),D).EQ.0 !Filter.
& .AND. (MOD(H3 + MOD(-P1**2,H3),H3) .EQ. MOD(D,H3))) THEN !Beware MOD for negative numbers! MOD(-P1**2, may surprise...
P2 = 1 + (P1 - 1)*(H3 + P1)/D !Candidate for the second prime.
IF (ISPRIME(P2)) THEN !Is it prime?
P3 = 1 + P1*P2/H3 !Yes. Candidate for the third prime.
IF (ISPRIME(P3)) THEN !Is it prime?
IF (MOD(P2*P3,P1 - 1).EQ.1) THEN !Yes! Final test.
WRITE (MSG,2) P1,P2,P3, INT8(P1)*P2*P3 !Result!
2 FORMAT (3I6,I12)
END IF
END IF
END IF
END IF
END DO
END DO
END IF
END DO
END</syntaxhighlight>
 
===Output===
<pre>
Carmichael numbers that are the product of three primes:
P1 x P2 x P3 = C
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
</pre>
 
=={{header|Go}}==
<syntaxhighlight lang="go">package main
 
import "fmt"
 
// Use this rather than % for negative integers
func mod(n, m int) int {
return ((n % m) + m) % m
}
 
func isPrime(n int) bool {
if n < 2 { return false }
if n % 2 == 0 { return n == 2 }
if n % 3 == 0 { return n == 3 }
d := 5
for d * d <= n {
if n % d == 0 { return false }
d += 2
if n % d == 0 { return false }
d += 4
}
return true
}
 
func carmichael(p1 int) {
for h3 := 2; h3 < p1; h3++ {
for d := 1; d < h3 + p1; d++ {
if (h3 + p1) * (p1 - 1) % d == 0 && mod(-p1 * p1, h3) == d % h3 {
p2 := 1 + (p1 - 1) * (h3 + p1) / d
if !isPrime(p2) { continue }
p3 := 1 + p1 * p2 / h3
if !isPrime(p3) { continue }
if p2 * p3 % (p1 - 1) != 1 { continue }
c := p1 * p2 * p3
fmt.Printf("%2d %4d %5d %d\n", p1, p2, p3, c)
}
}
}
}
 
func main() {
fmt.Println("The following are Carmichael munbers for p1 <= 61:\n")
fmt.Println("p1 p2 p3 product")
fmt.Println("== == == =======")
 
for p1 := 2; p1 <= 61; p1++ {
if isPrime(p1) { carmichael(p1) }
}
}</syntaxhighlight>
 
{{out}}
<pre>
The following are Carmichael munbers for p1 <= 61:
 
p1 p2 p3 product
== == == =======
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
</pre>
=={{header|Haskell}}==
{{trans|Ruby}}
Line 313 ⟶ 1,720:
{{Works with|GHC|7.4.1}}
{{Works with|primes|0.2.1.0}}
<langsyntaxhighlight lang="haskell">#!/usr/bin/runhaskell
 
import Data.Numbers.Primes
Line 330 ⟶ 1,737:
return (p, q, r)
 
main = putStr $ unlines $ map show carmichaels</langsyntaxhighlight>
{{out}}
<pre>
Line 403 ⟶ 1,810:
(61,3361,4021)
</pre>
 
=={{header|Icon}} and {{header|Unicon}}==
 
The following works in both languages.
<langsyntaxhighlight lang="unicon">link "factors"
 
procedure main(A)
Line 430 ⟶ 1,836:
procedure format(p1,p2,p3)
return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)
end</langsyntaxhighlight>
 
Output, with middle lines elided:
Line 464 ⟶ 1,870:
->
</pre>
=={{header|J}}==
 
<syntaxhighlight lang="j">
q =: (,"0 1~ >:@i.@<:@+/"1)&.>@(,&.>"0 1~ >:@i.)&.>@I.@(1&p:@i.)@>:
f1 =: (0: = {. | <:@{: * 1&{ + {:) *. ((1&{ | -@*:@{:) = 1&{ | {.)
f2 =: 1: = <:@{. | ({: * 1&{)
p2 =: 0:`((* 1&p:)@(<.@(1: + <:@{: * {. %~ 1&{ + {:)))@.f1
p3 =: 3:$0:`((* 1&p:)@({: , {. , (<.@>:@(1&{ %~ {. * {:))))@.(*@{.)@(p2 , }.)
(-. 3:$0:)@(((*"0 f2)@p3"1)@;@;@q) 61
</syntaxhighlight>
Output
<pre>
3 11 17
5 29 73
5 17 29
5 13 17
7 19 67
7 31 73
7 13 31
7 23 41
7 73 103
7 13 19
13 61 397
13 37 241
13 97 421
13 37 97
13 37 61
17 41 233
17 353 1201
19 43 409
19 199 271
23 199 353
29 113 1093
29 197 953
31 991 15361
31 61 631
31 151 1171
31 61 271
31 61 211
31 271 601
31 181 331
37 109 2017
37 73 541
37 613 1621
37 73 181
37 73 109
41 1721 35281
41 881 12041
41 101 461
41 241 761
41 241 521
41 73 137
41 61 101
43 631 13567
43 271 5827
43 127 2731
43 127 1093
43 211 757
43 631 1597
43 127 211
43 211 337
43 433 643
43 547 673
43 3361 3907
47 3359 6073
47 1151 1933
47 3727 5153
53 157 2081
53 79 599
53 157 521
59 1451 2089
61 421 12841
61 181 5521
61 1301 19841
61 277 2113
61 181 1381
61 541 3001
61 661 2521
61 271 571
61 241 421
61 3361 4021
</pre>
=={{header|Java}}==
{{trans|D}}
<langsyntaxhighlight lang="java">public class Test {
 
static int mod(int n, int m) {
Line 505 ⟶ 1,991:
}
}
}</langsyntaxhighlight>
<pre>3 x 11 x 17
5 x 29 x 73
Line 575 ⟶ 2,061:
61 x 241 x 421
61 x 3361 x 4021</pre>
 
=={{header|Julia}}==
This solution is a straightforward implementation of the algorithm of the Jameson paper cited in the task description. Just for fun, I use Julia's capacity to accommodate Unicode identifiers to match some of the paper's symbols to the variables used in the <tt>carmichael</tt> function.
 
'''Function'''
<syntaxhighlight lang="julia">using Primes
<lang Julia>
 
function carmichael{T<:Integer}(pmax::T)
function carmichael(pmax::Integer)
0 < pmax || throw(DomainError())
if pmax ≤ 0 throw(DomainError("pmax must be strictly positive")) end
car = T[]
car = Vector{typeof(pmax)}(0)
for p in primes(pmax)
for h₃ in 2:(p-1)
m = (p - 1) * (h₃ + p)
pmh = mod(-p ^ 2, h₃)
for Δ in 1:(h₃+p-1)
if m % Δ !== 0 &&|| Δ % h₃ !== pmh || continue end
q = div(m, ÷ Δ) + 1
if !isprime(q) || continue end
r = div((p * q - 1), ÷ h₃) + 1
if !isprime(r) &&|| mod(q * r, (p - 1)) == 1 ||continue continueend
append!(car, [p, q, r])
end
end
end
return reshape(car, 3, div(length(car), ÷ 3))
end</syntaxhighlight>
end
</lang>
 
'''Main'''
<syntaxhighlight lang="julia">hi = 61
<lang Julia>
hi = 61
car = carmichael(hi)
 
curp = tcnt = 0
print("Carmichael 3 (p×q×r) pseudoprimes, up to p = $hi:")
tcnt = 0
print("Carmichael 3 (p\u00d7q\u00d7r) Pseudoprimes, up to p = ", hi, ":")
for j in sortperm(1:size(car)[2], by=x->(car[1,x], car[2,x], car[3,x]))
p, q, r = car[:, j]
c = prod(car[:, j])
if p != curp
curp = p
print(@sprintfprintf("\n\np = %d\n ", p))
tcnt = 0
end
Line 624 ⟶ 2,107:
tcnt += 1
end
print(@sprintfprintf("p\u00d7p× %d\u00d7 × %d = %d ", q, r, c))
end
println("\n\n", size(car)[2], " results in total.")</syntaxhighlight>
</lang>
 
{{out}}
<pre>Carmichael 3 (p×q×r) pseudoprimes, up to p = 61:
<pre>
Carmichael 3 (p×q×r) Pseudoprimes, up to p = 61:
 
p = 3
p×11×17 = 561
 
p = 5
p×13×17 = 1105 p×17×29 = 2465 p×29×73 = 10585
 
p = 7
p×13×19 = 1729 p×13×31 = 2821 p×19×67 = 8911 p×23×41 = 6601
p×31×73 = 15841 p×73×103 = 52633
 
p = 1311
p×37×61p× =29 29341× p×37×97107 = 4665734133 p×37×241 =p× 11592137 × p×61×39759 = 31482124013
p×97×421 = 530881
 
p = 17
p×41×233p× 23 × 79 = 16240130889 p× 53 × p×353×1201101 = 720720191001
 
p = 19
p× 59 × 113 = 126673 p× 139 × 661 = 1745701 p× 193 × 283 = 1037761
p×43×409 = 334153 p×199×271 = 1024651
 
p = 23
p× 43 × 53 = 52417 p× 59 × 227 = 308039 p× 71 × 137 = 223721 p× 83 × 107 = 204263
p×199×353 = 1615681
 
p = 29
p× 41 × 109 = 129601 p× 89 × 173 = 446513 p× 97 × 149 = 419137 p× 149 × 541 = 2337661
p×113×1093 = 3581761 p×197×953 = 5444489
 
p = 31
p× 67 × 1039 = 2158003 p× 73 × 79 = 178777 p× 79 × 307 = 751843 p× 223 × 1153 = 7970689
p×61×211 = 399001 p×61×271 = 512461 p×61×631 = 1193221 p×151×1171 = 5481451
p× 313 × 463 = 4492489
p×181×331 = 1857241 p×271×601 = 5049001 p×991×15361 = 471905281
 
p = 37
p×73×109 = 294409 p×73×181 = 488881 p×73×541 = 1461241 p×109×2017 = 8134561
p×613×1621 = 36765901
 
p = 41
p× 89 × 1217 = 4440833 p× 97 × 569 = 2262913
p×61×101 = 252601 p×73×137 = 410041 p×101×461 = 1909001 p×241×521 = 5148001
p×241×761 = 7519441 p×881×12041 = 434932961 p×1721×35281 = 2489462641
 
p = 43
p× 67 × 241 = 694321 p× 107 × 461 = 2121061 p× 131 × 257 = 1447681 p× 139 × 1993 = 11912161
p×127×211 = 1152271 p×127×1093 = 5968873 p×127×2731 = 14913991 p×211×337 = 3057601
p× 157 × 751 = 5070001 p× 199 × 373 = 3191761
p×211×757 = 6868261 p×271×5827 = 67902031 p×433×643 = 11972017 p×547×673 = 15829633
p×631×1597 = 43331401 p×631×13567 = 368113411 p×3361×3907 = 564651361
 
p = 47
p× 53 × 499 = 1243009 p× 89 × 103 = 430849 p× 101 × 1583 = 7514501 p× 107 × 839 = 4219331
p×1151×1933 = 104569501 p×3359×6073 = 958762729 p×3727×5153 = 902645857
p× 157 × 239 = 1763581
 
p = 53
p× 113 × 1997 = 11960033 p× 197 × 233 = 2432753 p× 281 × 877 = 13061161
p×79×599 = 2508013 p×157×521 = 4335241 p×157×2081 = 17316001
 
p = 59
p× 131 × 1289 = 9962681 p× 139 × 821 = 6733021 p× 149 × 587 = 5160317 p× 173 × 379 = 3868453
p×1451×2089 = 178837201
p× 179 × 353 = 3728033
 
p = 61
p× 1009 × 2677 = 164766673
p×181×1381 = 15247621 p×181×5521 = 60957361 p×241×421 = 6189121 p×271×571 = 9439201
p×277×2113 = 35703361 p×421×12841 = 329769721 p×541×3001 = 99036001 p×661×2521 = 101649241
p×1301×19841 = 1574601601 p×3361×4021 = 824389441
 
6942 results in total.</pre>
=={{header|Kotlin}}==
</pre>
{{trans|D}}
<syntaxhighlight lang="scala">fun Int.isPrime(): Boolean {
return when {
this == 2 -> true
this <= 1 || this % 2 == 0 -> false
else -> {
val max = Math.sqrt(toDouble()).toInt()
(3..max step 2)
.filter { this % it == 0 }
.forEach { return false }
true
}
}
}
 
fun mod(n: Int, m: Int) = ((n % m) + m) % m
 
fun main(args: Array<String>) {
for (p1 in 3..61) {
if (p1.isPrime()) {
for (h3 in 2 until p1) {
val g = h3 + p1
for (d in 1 until g) {
if ((g * (p1 - 1)) % d == 0 && mod(-p1 * p1, h3) == d % h3) {
val q = 1 + (p1 - 1) * g / d
if (q.isPrime()) {
val r = 1 + (p1 * q / h3)
if (r.isPrime() && (q * r) % (p1 - 1) == 1) {
println("$p1 x $q x $r")
}
}
}
}
}
}
}
}</syntaxhighlight>
{{out}}
See D output.
=={{header|Lua}}==
<syntaxhighlight lang="lua">local function isprime(n)
if n < 2 then return false end
if n % 2 == 0 then return n==2 end
if n % 3 == 0 then return n==3 end
local f, limit = 5, math.sqrt(n)
while (f <= limit) do
if n % f == 0 then return false end; f=f+2
if n % f == 0 then return false end; f=f+4
end
return true
end
 
local function carmichael3(p)
local list = {}
if not isprime(p) then return list end
for h = 2, p-1 do
for d = 1, h+p-1 do
if ((h + p) * (p - 1)) % d == 0 and (-p * p) % h == (d % h) then
local q = 1 + math.floor((p - 1) * (h + p) / d)
if isprime(q) then
local r = 1 + math.floor(p * q / h)
if isprime(r) and (q * r) % (p - 1) == 1 then
list[#list+1] = { p=p, q=q, r=r }
end
end
end
end
end
return list
end
 
local found = 0
for p = 2, 61 do
local list = carmichael3(p)
found = found + #list
table.sort(list, function(a,b) return (a.p<b.p) or (a.p==b.p and a.q<b.q) or (a.p==b.p and a.q==b.q and a.r<b.r) end)
for k,v in ipairs(list) do
print(string.format("%.f × %.f × %.f = %.f", v.p, v.q, v.r, v.p*v.q*v.r))
end
end
print(found.." found.")</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">3 × 11 × 17 = 561
5 × 13 × 17 = 1105
5 × 17 × 29 = 2465
5 × 29 × 73 = 10585
7 × 13 × 19 = 1729
7 × 13 × 31 = 2821
7 × 19 × 67 = 8911
7 × 23 × 41 = 6601
7 × 31 × 73 = 15841
7 × 73 × 103 = 52633
13 × 37 × 61 = 29341
13 × 37 × 97 = 46657
13 × 37 × 241 = 115921
13 × 61 × 397 = 314821
13 × 97 × 421 = 530881
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 × 61 × 211 = 399001
31 × 61 × 271 = 512461
31 × 61 × 631 = 1193221
31 × 151 × 1171 = 5481451
31 × 181 × 331 = 1857241
31 × 271 × 601 = 5049001
31 × 991 × 15361 = 471905281
37 × 73 × 109 = 294409
37 × 73 × 181 = 488881
37 × 73 × 541 = 1461241
37 × 109 × 2017 = 8134561
37 × 613 × 1621 = 36765901
41 × 61 × 101 = 252601
41 × 73 × 137 = 410041
41 × 101 × 461 = 1909001
41 × 241 × 521 = 5148001
41 × 241 × 761 = 7519441
41 × 881 × 12041 = 434932961
41 × 1721 × 35281 = 2489462641
43 × 127 × 211 = 1152271
43 × 127 × 1093 = 5968873
43 × 127 × 2731 = 14913991
43 × 211 × 337 = 3057601
43 × 211 × 757 = 6868261
43 × 271 × 5827 = 67902031
43 × 433 × 643 = 11972017
43 × 547 × 673 = 15829633
43 × 631 × 1597 = 43331401
43 × 631 × 13567 = 368113411
43 × 3361 × 3907 = 564651361
47 × 1151 × 1933 = 104569501
47 × 3359 × 6073 = 958762729
47 × 3727 × 5153 = 902645857
53 × 79 × 599 = 2508013
53 × 157 × 521 = 4335241
53 × 157 × 2081 = 17316001
59 × 1451 × 2089 = 178837201
61 × 181 × 1381 = 15247621
61 × 181 × 5521 = 60957361
61 × 241 × 421 = 6189121
61 × 271 × 571 = 9439201
61 × 277 × 2113 = 35703361
61 × 421 × 12841 = 329769721
61 × 541 × 3001 = 99036001
61 × 661 × 2521 = 101649241
61 × 1301 × 19841 = 1574601601
61 × 3361 × 4021 = 824389441
69 found.</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight lang="mathematica">Cases[Cases[
Cases[Table[{p1, h3, d}, {p1, Array[Prime, PrimePi@61]}, {h3, 2,
p1 - 1}, {d, 1, h3 + p1 - 1}], {p1_Integer, h3_, d_} /;
Line 701 ⟶ 2,317:
Infinity], {p1_, p2_, h3_} /; PrimeQ[1 + Floor[p1 p2/h3]] :> {p1,
p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /;
Mod[p2 p3, p1 - 1] == 1 :> Print[p1, "*", p2, "*", p3]]</langsyntaxhighlight>
=={{header|Nim}}==
{{trans|Vala}} with some modifications
<syntaxhighlight lang="nim">import strformat
 
func isPrime(n: int64): bool =
if n == 2 or n == 3:
return true
elif n < 2 or n mod 2 == 0 or n mod 3 == 0:
return false
var `div` = 5i64
var `inc` = 2i64
while `div` * `div` <= n:
if n mod `div` == 0:
return false
`div` += `inc`
`inc` = 6 - `inc`
return true
 
for p in 2i64 .. 61:
if not isPrime(p):
continue
for h3 in 2i64 ..< p:
var g = h3 + p
for d in 1 ..< g:
if g * (p - 1) mod d != 0 or (d + p * p) mod h3 != 0:
continue
var q = 1 + (p - 1) * g div d
if not isPrime(q):
continue
var r = 1 + (p * q div h3)
if not isPrime(r) or (q * r) mod (p - 1) != 1:
continue
echo &"{p:5} × {q:5} × {r:5} = {p * q * r:10}"</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">f(p)={
my(v=List(),q,r);
for(h=2,p-1,
Line 715 ⟶ 2,435:
Set(v)
};
forprime(p=3,67,v=f(p); for(i=1,#v,print1(v[i]", ")))</langsyntaxhighlight>
{{out}}
<pre>561, 1105, 2465, 10585, 1729, 2821, 6601, 8911, 15841, 52633, 29341, 46657, 115921, 314821, 530881, 162401, 7207201, 334153, 1024651, 1615681, 3581761, 5444489, 399001, 512461, 1193221, 1857241, 5049001, 5481451, 471905281, 294409, 488881, 1461241, 8134561, 36765901, 252601, 410041, 1909001, 5148001, 7519441, 434932961, 2489462641, 1152271, 3057601, 5968873, 6868261, 11972017, 14913991, 15829633, 43331401, 67902031, 368113411, 564651361, 104569501, 902645857, 958762729, 2508013, 4335241, 17316001, 178837201, 6189121, 9439201, 15247621, 35703361, 60957361, 99036001, 101649241, 329769721, 824389441, 1574601601, 10267951, 163954561, 7991602081,</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/forprimes is_prime vecprod/;
 
forprimes { my $p = $_;
Line 737 ⟶ 2,456:
}
}
} 3,61;</langsyntaxhighlight>
{{out}}
<pre>
Line 750 ⟶ 2,469:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Phix}}==
 
<!--<syntaxhighlight lang="phix">(phixonline)-->
=={{header|Perl 6}}==
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
{{works with|Rakudo|2015.12}}
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
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. (Perl 6 uses arbitrary precision in any case.)
<span style="color: #008080;">for</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">61</span> <span style="color: #008080;">do</span>
<lang perl6>for (2..67).grep: *.is-prime -> \Prime1 {
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
for 1 ^..^ Prime1 -> \h3 {
<span style="color: #008080;">for</span> <span style="color: #000000;">h3</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">p1</span> <span style="color: #008080;">do</span>
my \g = h3 + Prime1;
<span style="color: #004080;">atom</span> <span style="color: #000000;">h3p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h3</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">p1</span>
for 0 ^..^ h3 + Prime1 -> \d {
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h3p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
if (h3 + Prime1) * (Prime1 - 1) %% d and -Prime1**2 % h3 == d % h3 {
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h3p1</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span>
my \Prime2 = floor 1 + (Prime1 - 1) * g / d;
<span style="color: #008080;">and</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(-(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">h3</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
next unless Prime2.is-prime;
<span style="color: #004080;">atom</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(((</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">h3p1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">),</span>
my \Prime3 = floor 1 + Prime1 * Prime2 / h3;
<span style="color: #000000;">p3</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">/</span><span style="color: #000000;">h3</span><span style="color: #0000FF;">)</span>
next unless Prime3.is-prime;
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
next unless (Prime2 * Prime3) % (Prime1 - 1) == 1;
<span style="color: #008080;">and</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p3</span><span style="color: #0000FF;">)</span>
say "{Prime1} × {Prime2} × {Prime3} == {Prime1 * Prime2 * Prime3}";
<span style="color: #008080;">and</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
}
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">5</span> <span style="color: #008080;">or</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">></span><span style="color: #000000;">65</span> <span style="color: #008080;">then</span>
}
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d * %d * %d = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p3</span><span style="color: #0000FF;">})</span>
}
<span style="color: #008080;">elsif</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">35</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"...\n"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
}</lang>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d Carmichael numbers found\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
<pre>3 × 11 × 17 == 561
53 ×* 2911 ×* 7317 == 10585561
5 ×* 1729 ×* 2973 == 246510585
5 ×* 1317 ×* 1729 == 11052465
75 ×* 1913 ×* 6717 == 89111105
7 ×* 3119 ×* 7367 == 158418911
...
7 × 13 × 31 == 2821
761 ×* 23271 ×* 41571 == 66019439201
761 ×* 73241 ×* 103421 == 526336189121
761 ×* 133361 ×* 194021 == 1729824389441
69 Carmichael numbers found
13 × 61 × 397 == 314821
</pre>
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</pre>
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de modulo (X Y)
(% (+ Y (% X Y)) Y) )
Line 883 ⟶ 2,550:
(prinl)
(bye)</langsyntaxhighlight>
 
=={{header|PL/I}}==
<langsyntaxhighlight PLlang="pl/Ii">Carmichael: procedure options (main, reorder); /* 24 January 2014 */
declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);
 
Line 912 ⟶ 2,578:
/* Uses is_prime from Rosetta Code PL/I. */
 
end Carmichael;</langsyntaxhighlight>
Results:
<pre>
Line 1,009 ⟶ 2,675:
61 x 3361 x 4021
</pre>
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
show(Limit) :-
forall(
carmichael(Limit, P1, P2, P3, C),
format("~w * ~w * ~w ~t~20| = ~w~n", [P1, P2, P3, C])).
 
carmichael(Upto, P1, P2, P3, X) :-
between(2, Upto, P1),
prime(P1),
Limit is P1 - 1, between(2, Limit, H3),
MaxD is H3 + P1 - 1, between(1, MaxD, D),
(H3 + P1)*(P1 - 1) mod D =:= 0,
-P1*P1 mod H3 =:= D mod H3,
P2 is 1 + (P1 - 1)*(H3 + P1) div D,
prime(P2),
P3 is 1 + P1*P2 div H3,
prime(P3),
X is P1*P2*P3.
 
wheel235(L) :-
W = [4, 2, 4, 2, 4, 6, 2, 6 | W],
L = [1, 2, 2 | W].
 
prime(N) :-
N >= 2,
wheel235(W),
prime(N, 2, W).
 
prime(N, D, _) :- D*D > N, !.
prime(N, D, [A|As]) :-
N mod D =\= 0,
D2 is D + A, prime(N, D2, As).
</syntaxhighlight>
{{Out}}
<pre>
?- show(61).
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
11 * 29 * 107 = 34133
11 * 37 * 59 = 24013
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
17 * 23 * 79 = 30889
17 * 53 * 101 = 91001
19 * 43 * 409 = 334153
19 * 139 * 661 = 1745701
19 * 59 * 113 = 126673
19 * 193 * 283 = 1037761
19 * 199 * 271 = 1024651
23 * 59 * 227 = 308039
23 * 71 * 137 = 223721
23 * 199 * 353 = 1615681
23 * 83 * 107 = 204263
23 * 43 * 53 = 52417
29 * 113 * 1093 = 3581761
29 * 197 * 953 = 5444489
29 * 149 * 541 = 2337661
29 * 41 * 109 = 129601
29 * 89 * 173 = 446513
29 * 97 * 149 = 419137
31 * 991 * 15361 = 471905281
31 * 67 * 1039 = 2158003
31 * 61 * 631 = 1193221
31 * 151 * 1171 = 5481451
31 * 223 * 1153 = 7970689
31 * 61 * 271 = 512461
31 * 79 * 307 = 751843
31 * 61 * 211 = 399001
31 * 271 * 601 = 5049001
31 * 181 * 331 = 1857241
31 * 313 * 463 = 4492489
31 * 73 * 79 = 178777
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 * 89 * 1217 = 4440833
41 * 97 * 569 = 2262913
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 * 139 * 1993 = 11912161
43 * 127 * 1093 = 5968873
43 * 157 * 751 = 5070001
43 * 107 * 461 = 2121061
43 * 211 * 757 = 6868261
43 * 67 * 241 = 694321
43 * 631 * 1597 = 43331401
43 * 131 * 257 = 1447681
43 * 199 * 373 = 3191761
43 * 127 * 211 = 1152271
43 * 211 * 337 = 3057601
43 * 433 * 643 = 11972017
43 * 547 * 673 = 15829633
43 * 3361 * 3907 = 564651361
47 * 101 * 1583 = 7514501
47 * 53 * 499 = 1243009
47 * 107 * 839 = 4219331
47 * 3359 * 6073 = 958762729
47 * 1151 * 1933 = 104569501
47 * 157 * 239 = 1763581
47 * 3727 * 5153 = 902645857
47 * 89 * 103 = 430849
53 * 113 * 1997 = 11960033
53 * 157 * 2081 = 17316001
53 * 79 * 599 = 2508013
53 * 157 * 521 = 4335241
53 * 281 * 877 = 13061161
53 * 197 * 233 = 2432753
59 * 131 * 1289 = 9962681
59 * 139 * 821 = 6733021
59 * 149 * 587 = 5160317
59 * 173 * 379 = 3868453
59 * 179 * 353 = 3728033
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 * 1009 * 2677 = 164766673
61 * 271 * 571 = 9439201
61 * 241 * 421 = 6189121
61 * 3361 * 4021 = 824389441
true.
</pre>
=={{header|Python}}==
<langsyntaxhighlight lang="python">class Isprime():
'''
Extensible sieve of Eratosthenes
Line 1,081 ⟶ 2,896:
ans = sorted(sum((carmichael(n) for n in range(62) if isprime(n)), []))
print(',\n'.join(repr(ans[i:i+5])[1:-1] for i in range(0, len(ans)+1, 5)))</langsyntaxhighlight>
{{out}}
<pre>(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19),
Line 1,097 ⟶ 2,912:
(61, 181, 5521), (61, 241, 421), (61, 271, 571), (61, 277, 2113), (61, 421, 12841),
(61, 541, 3001), (61, 661, 2521), (61, 1301, 19841), (61, 3361, 4021)</pre>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
(require math)
Line 1,116 ⟶ 2,930:
(displayln (list p1 p2 p3 '=> (* p1 p2 p3))))))
(next (+ d 1))))))
</syntaxhighlight>
</lang>
Output:
<langsyntaxhighlight lang="racket">
(3 11 17 => 561)
(5 29 73 => 10585)
Line 1,181 ⟶ 2,995:
(61 241 421 => 6189121)
(61 3361 4021 => 824389441)
</syntaxhighlight>
</lang>
=={{header|Raku}}==
 
(formerly Perl 6)
{{works with|Rakudo|2015.12}}
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.)
<syntaxhighlight lang="raku" line>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}";
}
}
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|REXX}}==
===vertical list===
Note that REXX's version of &nbsp; '''modulus''' &nbsp; (<big><code>'''//'''</code></big>) &nbsp; is really a &nbsp; ''remainder'' &nbsp; function.
 
Line 1,190 ⟶ 3,094:
 
Some code optimization was done, while not necessary for the small default number ('''61'''), &nbsp; it was significant for larger numbers.
<langsyntaxhighlight lang="rexx">/*REXX program calculates Carmichael 3─strong pseudoprimes (up to and including N). */
numeric digits 18 /*handle big dig #s (9 is the default).*/
parse arg N .; if N=='' | N=="," then N=61 /*allow user to specify for the search.*/
tell= N>0; N= abs(N) /*N>0? Then display Carmichael numbers*/
carms#= 0 /*number of Carmichael numbers so far. */
!@.=0; !@.2=1; !@.3=1; !@.5=1; !@.7=1; !@.11=1; !@.13=1; !@.17=1; !@.19=1; !@.23=1; !@.29=1; !@.31=1
/*[↑] prime number memoization array. */
do p=3 to N by 2; pm= p-1; bot=0; top=0 /*step through some (odd) prime numbers*/
nps=-p*p; if \isPrime(p) then iterate; nps= -p*p /*is P a prime? No, then skip it.*/
c.= 0 /*the list of Carmichael #'s (so far).*/
@.=0
do h3=2 tofor pm-1; g= h3 + p /*findget Carmichael #s numbers for this prime. */
gPM=g*pm; npsH3= ((nps // h3) + h3) // h3 /*define a couple of shortcuts for pgm.*/
gPM= g * pm /*define a couple of shortcuts for pgm.*/
/* [↓] perform some weeding of D values*/
do d=1 for g-1; if gPM // d \== 0 then iterate
if npsH3 \== d//h3 then iterate
q= 1 + gPM q=1+gPM% d; if \isPrime(q) then iterate
r= 1 + r=1+p * q % h3; if q * r // pm \==1 1 then iterate
if \isPrime(r) then iterate
carms#=carms # + 1; @c.q= r /*bump Carmichael counter; add to array*/
if bot==0 then bot= q; bot= min(bot, q); top= max(top, q)
end /*d*/ /* [↑] find the minimum & the maximum.*/
end /*h3*/
$=0 /*display abuild list of some Carmichael #s.numbers*/
if tell then do j=bot to top by 2; while tell; if @c.j\==0 then iterate; $= $ $=1p"∙"j'∙'c.j
say 'Carmichael number: ' p end "∙" j '∙' @./*j*/
 
end /*j*/
if $\=='' then say 'Carmichael number: ' /*show a blank line for beautification.*/strip($)
end /*p*/
say
say '──────── ' carms # " Carmichael numbers found."
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrime: parse arg x; if !@.x then return 1 /*is X a known prime?*/
if x<37 then return 0; if x//2==0 then return 0; if x// 3==0 then return 0
parse var x '' -1 _; if _==5 then return 0; if x// 7==0 then return 0
if x//11==0 then return 0; if x//13==0 then return 0; if x//1317==0 then return 0
if x//1719==0 then return 0; if x//23==0 then return 0; if x//1929==0 then return 0
do k=2329 by 6 until k*k>x; if x// k ==0 then return 0
if x//(k+2) ==0 then return 0
end end /*ik*/
!@.x=1; return 1</langsyntaxhighlight>
'''output''' &nbsp; when using the default input:
<pre>
<pre style="height:65ex">
Carmichael number: 3 ∙ 11 ∙ 173∙11∙17
Carmichael number: 5∙13∙17 5∙17∙29 5∙29∙73
 
Carmichael number: 57∙13∙19 ∙7∙19∙67 137∙23∙41 ∙7∙31∙73 177∙73∙103
Carmichael number: 513∙37∙61 ∙13∙61∙397 17 ∙ 2913∙97∙421
Carmichael number: 517∙41∙233 ∙ 29 ∙ 7317∙353∙1201
Carmichael number: 19∙43∙409 19∙199∙271
 
Carmichael number: 7 ∙ 13 ∙ 1923∙199∙353
Carmichael number: 729∙113∙1093 ∙ 19 ∙ 6729∙197∙953
Carmichael number: 731∙61∙211 ∙31∙151∙1171 2331∙181∙331 ∙31∙271∙601 4131∙991∙15361
Carmichael number: 737∙73∙109 ∙37∙109∙2017 31 ∙ 7337∙613∙1621
Carmichael number: 741∙61∙101 ∙41∙73∙137 7341∙101∙461 ∙41∙241∙521 10341∙881∙12041 41∙1721∙35281
Carmichael number: 43∙127∙211 43∙211∙337 43∙271∙5827 43∙433∙643 43∙547∙673 43∙631∙1597 43∙3361∙3907
 
Carmichael number: 1347∙1151∙1933 ∙47∙3359∙6073 37 ∙ 6147∙3727∙5153
Carmichael number: 1353∙79∙599 ∙ 61 ∙ 39753∙157∙521
Carmichael number: 13 ∙ 97 ∙ 42159∙1451∙2089
Carmichael number: 61∙181∙1381 61∙241∙421 61∙271∙571 61∙277∙2113 61∙421∙12841 61∙541∙3001 61∙661∙2521 61∙1301∙19841 61∙3361∙4021
 
Carmichael number: 17 ∙ 41 ∙ 233
Carmichael number: 17 ∙ 353 ∙ 1201
 
Carmichael number: 19 ∙ 43 ∙ 409
Carmichael number: 19 ∙ 199 ∙ 271
 
Carmichael number: 23 ∙ 199 ∙ 353
 
Carmichael number: 29 ∙ 113 ∙ 1093
Carmichael number: 29 ∙ 197 ∙ 953
 
Carmichael number: 31 ∙ 61 ∙ 211
Carmichael number: 31 ∙ 151 ∙ 1171
Carmichael number: 31 ∙ 181 ∙ 331
Carmichael number: 31 ∙ 271 ∙ 601
Carmichael number: 31 ∙ 991 ∙ 15361
 
Carmichael number: 37 ∙ 73 ∙ 109
Carmichael number: 37 ∙ 109 ∙ 2017
Carmichael number: 37 ∙ 613 ∙ 1621
 
Carmichael number: 41 ∙ 61 ∙ 101
Carmichael number: 41 ∙ 73 ∙ 137
Carmichael number: 41 ∙ 101 ∙ 461
Carmichael number: 41 ∙ 241 ∙ 521
Carmichael number: 41 ∙ 881 ∙ 12041
Carmichael number: 41 ∙ 1721 ∙ 35281
 
Carmichael number: 43 ∙ 127 ∙ 211
Carmichael number: 43 ∙ 211 ∙ 337
Carmichael number: 43 ∙ 271 ∙ 5827
Carmichael number: 43 ∙ 433 ∙ 643
Carmichael number: 43 ∙ 547 ∙ 673
Carmichael number: 43 ∙ 631 ∙ 1597
Carmichael number: 43 ∙ 3361 ∙ 3907
 
Carmichael number: 47 ∙ 1151 ∙ 1933
Carmichael number: 47 ∙ 3359 ∙ 6073
Carmichael number: 47 ∙ 3727 ∙ 5153
 
Carmichael number: 53 ∙ 79 ∙ 599
Carmichael number: 53 ∙ 157 ∙ 521
 
Carmichael number: 59 ∙ 1451 ∙ 2089
 
Carmichael number: 61 ∙ 181 ∙ 1381
Carmichael number: 61 ∙ 241 ∙ 421
Carmichael number: 61 ∙ 271 ∙ 571
Carmichael number: 61 ∙ 277 ∙ 2113
Carmichael number: 61 ∙ 421 ∙ 12841
Carmichael number: 61 ∙ 541 ∙ 3001
Carmichael number: 61 ∙ 661 ∙ 2521
Carmichael number: 61 ∙ 1301 ∙ 19841
Carmichael number: 61 ∙ 3361 ∙ 4021
 
 
──────── 69 Carmichael numbers found.
Line 1,315 ⟶ 3,165:
──────── 8716 Carmichael numbers found.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Carmichael 3 strong pseudoprimes
 
see "The following are Carmichael munbers for p1 <= 61:" + nl
===horizontal list===
see "p1 p2 p3 product" + nl
This REXX version (pre-)generates a number of primes to assist the &nbsp; '''isPrime''' &nbsp; function.
<lang rexx>/*REXX program calculates Carmichael 3─strong pseudoprimes (up to and including N). */
numeric digits 18 /*handle big dig #s (9 is the default).*/
parse arg N .; if N=='' then N=61 /*allow user to specify for the search.*/
tell= N>0; N=abs(N) /*N>0? Then display Carmichael numbers*/
carms=0 ; !.=0 /*number of Carmichael numbers so far. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1; !.29=1; !.31=1; !.37=1
HP=37; do i=HP+2 by 2 for N*20; if isPrime(i) then do; !.i=1; HP=i; end; end /*i*/
HP=HP+2
/*[↑] prime number memoization array. */
do p=3 to N by 2; pm=p-1; bot=0; top=0 /*step through some (odd) prime numbers*/
if \isPrime(p) then iterate; nps=-p*p /*is P a prime? No, then skip it.*/
@.=0
do h3=2 for pm-1; g=h3+p /*find Carmichael #s for this prime. */
gPM=g*pm; npsH3=((nps//h3)+h3)//h3 /*define a couple of shortcuts for pgm.*/
/* [↓] perform some weeding of D values*/
do d=1 for g-1; if gPM//d \== 0 then iterate
if npsH3 \== d//h3 then iterate
q=1+gPM%d; if \isPrime(q) then iterate
r=1+p*q%h3; if q*r//pm\==1 then iterate
if \isPrime(r) then iterate
carms=carms+1; @.q=r /*bump Carmichael counter; add to array*/
if bot==0 then bot=q; bot=min(bot,q); top=max(top,q)
end /*d*/ /* [↑] find the minimum & the maximum.*/
end /*h3*/
#= /*display a list of some Carmichael #s.*/
do j=bot to top by 2 while tell; if @.j==0 then iterate; #=#',' p"∙"j'∙'@.j
end /*j*/
if #\=='' then say 'Carmichael numbers:' strip(#,, ",")
end /*p*/
say
say '──────── ' carms " Carmichael numbers found."
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrime: parse arg x; if !.x then return 1 /*X a known prime?*/
if x<HP then return 0; if x//2==0 then return 0; if x// 3==0 then return 0
parse var x '' -1 _; if _==5 then return 0; if x// 7==0 then return 0
if x//11==0 then return 0; if x//13==0 then return 0
if x//17==0 then return 0; if x//19==0 then return 0
if x//23==0 then return 0; if x//29==0 then return 0
if x//31==0 then return 0; if x//37==0 then return 0
c=x /* ___*/
b=1; do while b<=x; b=b*4; end /*these two lines compute integer √ X */
s=0; do while b>1; b=b%4; _=c-s-b; s=s%2; if _>=0 then do; c=_; s=s+b; end; end
do k=41 by 6 to s; parse var k '' -1 _
if _\==5 then if x// k ==0 then return 0
if _\==3 then if x//(k+2)==0 then return 0
end /*k*/ /*K will never be divisible by three.*/
!.x=1; return 1 /*Define a new prime (X). Indicate so.*/</lang>
'''output''' &nbsp; when the following us used for input: &nbsp; <tt> 1000 </tt>
<pre style="height:72ex">
Carmichael numbers: 3∙11∙17
Carmichael numbers: 5∙13∙17, 5∙17∙29, 5∙29∙73
Carmichael numbers: 7∙13∙19, 7∙19∙67, 7∙23∙41, 7∙31∙73, 7∙73∙103
Carmichael numbers: 13∙37∙61, 13∙61∙397, 13∙97∙421
Carmichael numbers: 17∙41∙233, 17∙353∙1201
Carmichael numbers: 19∙43∙409, 19∙199∙271
Carmichael numbers: 23∙199∙353
Carmichael numbers: 29∙113∙1093, 29∙197∙953
Carmichael numbers: 31∙61∙211, 31∙151∙1171, 31∙181∙331, 31∙271∙601, 31∙991∙15361
Carmichael numbers: 37∙73∙109, 37∙109∙2017, 37∙613∙1621
Carmichael numbers: 41∙61∙101, 41∙73∙137, 41∙101∙461, 41∙241∙521, 41∙881∙12041, 41∙1721∙35281
Carmichael numbers: 43∙127∙211, 43∙211∙337, 43∙271∙5827, 43∙433∙643, 43∙547∙673, 43∙631∙1597, 43∙3361∙3907
Carmichael numbers: 47∙1151∙1933, 47∙3359∙6073, 47∙3727∙5153
Carmichael numbers: 53∙79∙599, 53∙157∙521
Carmichael numbers: 59∙1451∙2089
Carmichael numbers: 61∙181∙1381, 61∙241∙421, 61∙271∙571, 61∙277∙2113, 61∙421∙12841, 61∙541∙3001, 61∙661∙2521, 61∙1301∙19841, 61∙3361∙4021
Carmichael numbers: 67∙331∙463, 67∙2311∙51613
Carmichael numbers: 71∙271∙521, 71∙421∙491, 71∙631∙701, 71∙701∙5531, 71∙911∙9241
Carmichael numbers: 73∙157∙2293, 73∙379∙523, 73∙601∙21937, 73∙937∙13681
Carmichael numbers: 79∙2237∙25247
Carmichael numbers: 83∙2953∙4019, 83∙6971∙289297
Carmichael numbers: 89∙353∙617, 89∙617∙3433, 89∙881∙7129, 89∙4049∙120121
Carmichael numbers: 97∙193∙1249, 97∙673∙769, 97∙769∙10657, 97∙1201∙38833, 97∙2113∙5857
Carmichael numbers: 101∙151∙251, 101∙1301∙43801
Carmichael numbers: 103∙647∙1361, 103∙1123∙6427, 103∙3571∙183907, 103∙3877∙4591, 103∙5407∙185641
Carmichael numbers: 107∙743∙1061, 107∙3181∙26183
Carmichael numbers: 109∙163∙379, 109∙229∙4993, 109∙241∙2389, 109∙379∙919, 109∙433∙2053, 109∙541∙2269, 109∙1297∙12853, 109∙1657∙6229, 109∙1801∙4789
Carmichael numbers: 113∙337∙449, 113∙827∙18691, 113∙6833∙85793, 113∙8737∙22961
Carmichael numbers: 127∙631∙26713, 127∙659∙1373, 127∙991∙3313, 127∙2143∙30241, 127∙16633∙422479
Carmichael numbers: 131∙491∙4021, 131∙521∙2731, 131∙571∙1871, 131∙911∙2341, 131∙1171∙38351, 131∙1301∙8971, 131∙4421∙115831, 131∙5851∙191621, 131∙17291∙1132561
Carmichael numbers: 137∙409∙14009, 137∙953∙5441, 137∙3673∙20129, 137∙5441∙11833
Carmichael numbers: 139∙691∙829, 139∙3359∙66701, 139∙4003∙92737, 139∙4969∙8971, 139∙17389∙21391
Carmichael numbers: 149∙593∙29453, 149∙1481∙3109
Carmichael numbers: 151∙211∙541, 151∙331∙3571, 151∙601∙751, 151∙701∙1451, 151∙751∙8101, 151∙2551∙192601, 151∙4951∙53401
Carmichael numbers: 157∙313∙1093, 157∙937∙6397, 157∙1093∙15601, 157∙2017∙28789, 157∙4993∙11701, 157∙26053∙409033
Carmichael numbers: 163∙379∙2377, 163∙487∙811, 163∙811∙1297, 163∙1297∙42283, 163∙1621∙37747
Carmichael numbers: 167∙4483∙34031, 167∙29383∙490697
Carmichael numbers: 173∙1291∙31907, 173∙10321∙255077, 173∙36809∙155317
Carmichael numbers: 179∙1069∙4451, 179∙3739∙7121, 179∙9257∙57139, 179∙10859∙485941
Carmichael numbers: 181∙271∙9811, 181∙541∙3061, 181∙631∙811, 181∙733∙66337, 181∙1693∙43777, 181∙2953∙3637, 181∙3061∙9721, 181∙5881∙9421, 181∙11161∙15661, 181∙16561∙999181
Carmichael numbers: 191∙421∙431, 191∙571∙15581, 191∙1901∙7411, 191∙3877∙56963, 191∙12541∙342191
Carmichael numbers: 193∙257∙1601, 193∙401∙11057, 193∙577∙5569, 193∙1249∙2593, 193∙2689∙30529, 193∙7681∙211777, 193∙61057∙94273
Carmichael numbers: 199∙397∙4159, 199∙859∙2311, 199∙937∙20719, 199∙991∙32869, 199∙4159∙8713, 199∙8713∙82567
Carmichael numbers: 211∙281∙491, 211∙421∙631, 211∙631∙66571, 211∙1051∙9241, 211∙1741∙4651, 211∙1831∙4111, 211∙2311∙54181, 211∙2521∙3571, 211∙3221∙35771, 211∙3571∙9661, 211∙4019∙11159, 211∙4201∙98491, 211∙32341∙70351, 211∙68041∙127051
Carmichael numbers: 223∙1777∙23311, 223∙2221∙5107, 223∙5107∙37963, 223∙14653∙79699, 223∙25087∙1864801
Carmichael numbers: 227∙1583∙6781, 227∙2713∙5651, 227∙7459∙423299, 227∙21019∙91757
Carmichael numbers: 229∙457∙2053, 229∙571∙4219, 229∙1597∙182857, 229∙2243∙73379, 229∙7069∙32377
Carmichael numbers: 233∙5569∙185369
Carmichael numbers: 239∙409∙3911, 239∙1429∙1667, 239∙1667∙6427, 239∙32369∙234431
Carmichael numbers: 241∙337∙4513, 241∙433∙52177, 241∙1201∙2161, 241∙1361∙4001, 241∙2161∙3361, 241∙3361∙32401, 241∙5521∙110881, 241∙6481∙780961, 241∙7321∙588121, 241∙84961∙181201
Carmichael numbers: 251∙751∙3251, 251∙2251∙56501, 251∙3251∙4001, 251∙4751∙22501, 251∙16001∙803251, 251∙22501∙297251, 251∙31751∙2656501
Carmichael numbers: 257∙641∙1153, 257∙769∙49409, 257∙67073∙3447553, 257∙78593∙403969
Carmichael numbers: 263∙787∙2621, 263∙1049∙3407, 263∙6551∙12577, 263∙71527∙1881161
Carmichael numbers: 269∙1877∙126229, 269∙4289∙384581, 269∙10453∙65393, 269∙15277∙21977
Carmichael numbers: 271∙541∙811, 271∙811∙2971, 271∙1171∙7741, 271∙1801∙16831, 271∙2161∙65071, 271∙4591∙4861, 271∙4861∙77491, 271∙8191∙1109881, 271∙8641∙47791, 271∙9631∙52201, 271∙10531∙1426951, 271∙14797∙1336663
Carmichael numbers: 277∙829∙7177, 277∙1381∙1933, 277∙3313∙9661, 277∙6073∙31741, 277∙18493∙88321, 277∙19597∙36433
Carmichael numbers: 281∙421∙701, 281∙617∙673, 281∙1009∙4649, 281∙1321∙23201, 281∙4201∙9521, 281∙7121∙26681, 281∙9521∙13721, 281∙25621∙84701
Carmichael numbers: 283∙4231∙598687, 283∙17203∙58657
Carmichael numbers: 293∙877∙4673, 293∙1607∙31391, 293∙3943∙5987
Carmichael numbers: 307∙613∙919, 307∙919∙141067, 307∙1531∙3673, 307∙2143∙13159, 307∙3673∙225523, 307∙6427∙246637, 307∙17443∙153001, 307∙18973∙1941571
Carmichael numbers: 311∙1117∙26723, 311∙1303∙2357, 311∙2791∙21701, 311∙3659∙7069, 311∙23251∙33791, 311∙26041∙323951, 311∙28211∙165541, 311∙44641∙52391
Carmichael numbers: 313∙521∙23297, 313∙937∙58657, 313∙1093∙6709, 313∙1249∙55849, 313∙3433∙38377, 313∙3793∙395737, 313∙5449∙12097, 313∙6577∙8761, 313∙7177∙70201, 313∙9049∙472057, 313∙12637∙359581, 313∙49297∙5143321, 313∙51481∙947857, 313∙66457∙184081, 313∙129169∙400297
Carmichael numbers: 317∙18013∙41081, 317∙104281∙2542853
Carmichael numbers: 331∙661∙991, 331∙947∙24113, 331∙991∙4621, 331∙1321∙17491, 331∙2311∙12541, 331∙2971∙49171, 331∙3331∙551281, 331∙4051∙18121, 331∙4621∙14851, 331∙37181∙1758131, 331∙37951∙897271, 331∙41141∙316691
Carmichael numbers: 337∙421∙47293, 337∙449∙21617, 337∙673∙1009, 337∙953∙8681, 337∙1009∙3697, 337∙1597∙12517, 337∙2473∙11113, 337∙3697∙12097, 337∙16369∙1379089, 337∙19489∙597073, 337∙35393∙40433, 337∙58129∙2176609
Carmichael numbers: 347∙3461∙92383, 347∙4153∙29411
Carmichael numbers: 349∙929∙7541, 349∙1741∙2089, 349∙3191∙12239, 349∙4177∙20533, 349∙122149∙21315001
Carmichael numbers: 353∙617∙19801, 353∙1153∙5153, 353∙1321∙66617, 353∙13217∙77761, 353∙130241∙2704417
Carmichael numbers: 359∙43319∙3887881, 359∙46183∙592133
Carmichael numbers: 367∙733∙1831, 367∙1831∙9883, 367∙5003∙42701, 367∙9151∙419803, 367∙24889∙51607, 367∙28183∙574621
Carmichael numbers: 373∙1117∙1861, 373∙1613∙150413, 373∙5581∙1040857, 373∙16741∙81097, 373∙139501∙26016937
Carmichael numbers: 379∙631∙9199, 379∙757∙4159, 379∙2269∙24571, 379∙2539∙21871, 379∙6427∙202987, 379∙9829∙17011, 379∙10639∙268813
Carmichael numbers: 383∙33617∙40111, 383∙38201∙860647, 383∙74873∙3186263
Carmichael numbers: 389∙3299∙6791
Carmichael numbers: 397∙1783∙4951, 397∙2971∙51283, 397∙4357∙8317, 397∙30097∙56629, 397∙55837∙852589, 397∙79201∙10480933, 397∙99793∙370261
Carmichael numbers: 401∙641∙2161, 401∙1201∙1601, 401∙2161∙216641, 401∙2801∙9601, 401∙9521∙19681, 401∙9601∙70001, 401∙15601∙18401, 401∙18401∙567601, 401∙161201∙32320801
Carmichael numbers: 409∙2857∙6529, 409∙6121∙96289, 409∙6529∙22441, 409∙7039∙575791, 409∙35089∙683401, 409∙36721∙114649
Carmichael numbers: 419∙15467∙47653, 419∙22573∙78167, 419∙47653∙539639
Carmichael numbers: 421∙631∙11551, 421∙701∙2381, 421∙3851∙85331, 421∙7561∙289381, 421∙9661∙15121, 421∙13441∙209581, 421∙18481∙39901, 421∙20231∙54251, 421∙35533∙7479697, 421∙42589∙208489, 421∙89041∙12495421
Carmichael numbers: 431∙1721∙29671, 431∙1979∙142159, 431∙8171∙55901, 431∙13331∙168991
Carmichael numbers: 433∙937∙11593, 433∙1297∙2161, 433∙2161∙16417, 433∙2593∙48817, 433∙2953∙21673, 433∙3457∙6481, 433∙3697∙55201, 433∙6481∙87697
Carmichael numbers: 439∙3067∙673207, 439∙3943∙45553, 439∙9199∙2019181, 439∙10513∙17959, 439∙64679∙7098521, 439∙96799∙14164921
Carmichael numbers: 443∙1327∙4421, 443∙2029∙4967, 443∙74257∙143651, 443∙102103∙2380613, 443∙167077∙236471, 443∙251057∙889747
Carmichael numbers: 449∙2689∙3137, 449∙50849∙4566241, 449∙145601∙325249, 449∙202049∙45360001
Carmichael numbers: 457∙3877∙93253, 457∙5701∙8893, 457∙7297∙32377, 457∙15733∙19381, 457∙21433∙163249, 457∙28729∙55633, 457∙71593∙2337001, 457∙73721∙1203233, 457∙114001∙1211593
Carmichael numbers: 461∙691∙1151, 461∙1013∙38917, 461∙1381∙159161, 461∙3541∙23321, 461∙5981∙24841, 461∙26681∙4099981
Carmichael numbers: 463∙2927∙15401, 463∙6007∙39733, 463∙214831∙49733377, 463∙218527∙10117801
Carmichael numbers: 467∙141199∙474389
Carmichael numbers: 479∙57839∙219881
Carmichael numbers: 487∙1459∙8263, 487∙1531∙2683, 487∙1621∙1783, 487∙1783∙108541, 487∙8263∙9721, 487∙12637∙32563, 487∙17011∙2761453, 487∙26731∙110323, 487∙51517∙69499
Carmichael numbers: 491∙1471∙10781, 491∙6959∙569479, 491∙16661∙154351, 491∙41651∙46061, 491∙122501∙6683111, 491∙386611∙637001
Carmichael numbers: 499∙997∙4483, 499∙10459∙39841
Carmichael numbers: 503∙5021∙21587
Carmichael numbers: 509∙3557∙41149, 509∙7621∙23369, 509∙11939∙110491, 509∙86869∙11054081
Carmichael numbers: 521∙1301∙8581, 521∙21841∙41081
Carmichael numbers: 523∙1567∙163909, 523∙6091∙1592797, 523∙9397∙140419, 523∙15661∙481807, 523∙38629∙69427, 523∙155557∙1114471, 523∙193663∙462493
Carmichael numbers: 541∙811∙3511, 541∙1621∙7561, 541∙6661∙257401, 541∙7561∙54541, 541∙12421∙197641, 541∙16561∙814501
Carmichael numbers: 547∙1093∙2731, 547∙2731∙6553, 547∙6553∙35491, 547∙7333∙235951, 547∙26209∙186187, 547∙52963∙827737, 547∙158341∙2624623
Carmichael numbers: 557∙1669∙42257, 557∙38921∙7226333
Carmichael numbers: 563∙28663∙329333
Carmichael numbers: 569∙2273∙117577, 569∙13633∙1108169, 569∙17609∙25561, 569∙21017∙37489, 569∙22153∙787817
Carmichael numbers: 571∙661∙16411, 571∙2281∙2851, 571∙2851∙13681, 571∙6841∙43891, 571∙13681∙1562371, 571∙65323∙18649717
Carmichael numbers: 577∙757∙39709, 577∙1153∙6337, 577∙5569∙100417, 577∙6337∙26497, 577∙20161∙646273, 577∙32833∙37441, 577∙53857∙181729, 577∙79777∙86689, 577∙339841∙15083713, 577∙559297∙819073
Carmichael numbers: 587∙5861∙33403, 587∙9377∙54499, 587∙12893∙36919, 587∙49811∙3654883
Carmichael numbers: 593∙21017∙31081, 593∙35521∙3009137, 593∙176417∙34871761
Carmichael numbers: 599∙2393∙84319, 599∙120199∙17999801, 599∙179999∙35939801, 599∙266111∙547769, 599∙368369∙12979591
Carmichael numbers: 601∙1201∙1801, 601∙1801∙541201, 601∙3001∙200401, 601∙3121∙38281, 601∙3301∙5101, 601∙4201∙4801, 601∙4801∙412201, 601∙5101∙278701, 601∙6151∙7951, 601∙9001∙386401, 601∙19801∙28201, 601∙52201∙3921601, 601∙99901∙923701
Carmichael numbers: 607∙1213∙9091, 607∙4243∙1287751, 607∙21817∙322999, 607∙24847∙1885267, 607∙61813∙7504099, 607∙186649∙12588439, 607∙370873∙45023983, 607∙373903∙22695913
Carmichael numbers: 613∙919∙2143, 613∙1021∙312937, 613∙1327∙73951, 613∙1429∙23053, 613∙2857∙17341, 613∙7549∙87313, 613∙9181∙2813977, 613∙12241∙111997, 613∙51817∙213181, 613∙246637∙783361, 613∙364753∙386173
Carmichael numbers: 617∙661∙1013, 617∙8009∙705937, 617∙16633∙120737, 617∙29569∙2606297, 617∙59753∙81929, 617∙73613∙133981, 617∙129361∙6139673, 617∙137369∙1629937, 617∙383153∙47281081
Carmichael numbers: 619∙1237∙4327, 619∙2267∙26987, 619∙5563∙1721749, 619∙28429∙703903, 619∙53149∙56239, 619∙92083∙452377, 619∙398611∙9490009
Carmichael numbers: 631∙1471∙46411, 631∙5881∙90511, 631∙26209∙82279, 631∙32831∙67481
Carmichael numbers: 641∙4481∙7681, 641∙12161∙26881, 641∙17921∙370561, 641∙19841∙176641
Carmichael numbers: 643∙107857∙2391451
Carmichael numbers: 647∙4523∙19381, 647∙64601∙75583, 647∙188633∙532951, 647∙444449∙7013623
Carmichael numbers: 653∙13367∙2909551, 653∙176041∙732197
Carmichael numbers: 659∙2633∙5923, 659∙23689∙624443, 659∙27919∙34781, 659∙30269∙92779, 659∙73039∙6876101, 659∙92779∙1329161
Carmichael numbers: 661∙991∙131011, 661∙1321∙4621, 661∙2131∙4231, 661∙3191∙6491, 661∙3301∙12541, 661∙4621∙763621, 661∙5281∙81181, 661∙22111∙1623931, 661∙22441∙95701, 661∙138821∙152681
Carmichael numbers: 673∙1009∙14449, 673∙2017∙3361, 673∙3361∙12097, 673∙13441∙1292257, 673∙40801∙155137, 673∙231841∙9178177
Carmichael numbers: 677∙2029∙85853, 677∙4733∙1602121, 677∙6761∙25013, 677∙45293∙511057
Carmichael numbers: 683∙8867∙16369, 683∙11161∙206027, 683∙15749∙32303, 683∙42967∙2934647, 683∙94117∙9183131
Carmichael numbers: 691∙7591∙2622691, 691∙16561∙2288731, 691∙31051∙71761, 691∙34501∙2648911, 691∙69691∙3009781, 691∙743131∙1330321
Carmichael numbers: 701∙2801∙10501, 701∙3701∙1297201, 701∙3851∙899851, 701∙6301∙7001, 701∙18401∙58901, 701∙41651∙2245951, 701∙44101∙170801, 701∙46901∙319201, 701∙52501∙296801, 701∙53201∙632101
Carmichael numbers: 709∙4957∙12037, 709∙7789∙16993, 709∙9677∙21713, 709∙36109∙5120257, 709∙210277∙819157
Carmichael numbers: 719∙97649∙190271
Carmichael numbers: 727∙1453∙2179, 727∙2179∙792067, 727∙2663∙193601, 727∙3631∙8713, 727∙4423∙321553, 727∙176903∙32152121, 727∙308551∙1823713, 727∙651223∙2784937
Carmichael numbers: 733∙5857∙84181, 733∙13177∙47581, 733∙18301∙789097, 733∙22571∙2363507, 733∙25621∙9390097, 733∙150427∙1238911, 733∙271573∙22118113, 733∙631717∙3561913
Carmichael numbers: 739∙821∙4019, 739∙3691∙454609, 739∙10333∙2545363, 739∙62731∙1783009, 739∙152029∙1321759
Carmichael numbers: 743∙6679∙225569, 743∙6997∙9011, 743∙596569∙7266407
Carmichael numbers: 751∙2251∙10501, 751∙2851∙237901, 751∙21751∙181501, 751∙109751∙649001, 751∙123001∙1338751, 751∙153001∙1767751, 751∙191251∙10259251, 751∙318751∙2418001
Carmichael numbers: 757∙2017∙18397, 757∙2269∙858817, 757∙15121∙3815533, 757∙27541∙79273, 757∙32257∙2219869, 757∙33013∙59221, 757∙184843∙633151, 757∙627481∙6506893
Carmichael numbers: 761∙2129∙31769, 761∙2281∙3041, 761∙3041∙771401, 761∙6841∙19001, 761∙8969∙1137569, 761∙13681∙101081, 761∙19001∙1032841, 761∙41801∙497041, 761∙230281∙1184081, 761∙251941∙339341, 761∙314641∙497801
Carmichael numbers: 769∙6529∙9601, 769∙41729∙697601
Carmichael numbers: 773∙22003∙122363, 773∙44777∙47093
Carmichael numbers: 787∙3931∙9433, 787∙5503∙45589, 787∙106373∙3348623
Carmichael numbers: 797∙2389∙476009, 797∙3583∙16319, 797∙5573∙11941, 797∙21493∙428249, 797∙58109∙7718813, 797∙148853∙859681
Carmichael numbers: 809∙5657∙9697, 809∙78781∙176549, 809∙82013∙22116173, 809∙176549∙2197357, 809∙453289∙1171601
Carmichael numbers: 811∙1621∙438211, 811∙4051∙19441, 811∙4591∙744661, 811∙6481∙17011, 811∙19441∙3153331, 811∙77761∙1189891, 811∙86131∙478441
Carmichael numbers: 821∙1231∙6971, 821∙15581∙42641, 821∙137597∙6275953
Carmichael numbers: 823∙2467∙4111, 823∙4111∙23017, 823∙4933∙9043, 823∙27127∙637873, 823∙341953∙31269703
Carmichael numbers: 827∙2243∙2833, 827∙4957∙5783, 827∙24781∙476603, 827∙101009∙2880499, 827∙691363∙57175721
Carmichael numbers: 829∙1657∙17389, 829∙9109∙15733, 829∙10949∙2269181, 829∙24841∙1872109, 829∙140761∙5556709
Carmichael numbers: 839∙5867∙223747
Carmichael numbers: 853∙2557∙4261, 853∙7669∙594697, 853∙12781∙5451097, 853∙17041∙309277, 853∙19597∙185737
Carmichael numbers: 857∙6421∙127973, 857∙10273∙160073, 857∙95873∙115561, 857∙796937∙9229393
Carmichael numbers: 859∙2861∙3719, 859∙8581∙9439, 859∙9439∙150151, 859∙27457∙66067, 859∙321751∙1039039
Carmichael numbers: 863∙24137∙38791, 863∙28447∙153437, 863∙38791∙62927, 863∙56893∙68099
Carmichael numbers: 877∙1753∙56941, 877∙3067∙30223, 877∙6133∙8761, 877∙24091∙7042603, 877∙36793∙6453493, 877∙263677∙8894029
Carmichael numbers: 881∙2861∙840181, 881∙22441∙57641, 881∙130241∙16391761
Carmichael numbers: 883∙2647∙44101, 883∙8191∙267877, 883∙11467∙35281, 883∙15877∙824671, 883∙16633∙358219, 883∙21757∙3842287, 883∙30871∙134947, 883∙42337∙216091, 883∙126127∙161407, 883∙260191∙114874327, 883∙403957∙10808911, 883∙507151∙531847
Carmichael numbers: 887∙14177∙50503
Carmichael numbers: 907∙7853∙16007, 907∙137713∙24981139
Carmichael numbers: 911∙2003∙912367, 911∙9283∙1208117, 911∙9311∙55441, 911∙11831∙898171, 911∙16381∙28211, 911∙30941∙4026751, 911∙55511∙12642631, 911∙167441∙204751, 911∙175631∙2962961, 911∙185641∙1551551, 911∙227501∙2328691
Carmichael numbers: 919∙8263∙949213, 919∙15607∙170749, 919∙60589∙11136259, 919∙129439∙569161, 919∙156979∙321301, 919∙311203∙2918323, 919∙877609∙21797911
Carmichael numbers: 929∙5569∙23201, 929∙6961∙35729, 929∙42689∙1071841, 929∙139201∙307169
Carmichael numbers: 937∙1873∙70201, 937∙6553∙7489, 937∙7489∙1002457, 937∙21529∙3362113, 937∙38377∙5993209, 937∙177841∙820873
Carmichael numbers: 941∙5171∙23971, 941∙6581∙8461, 941∙8461∙361901, 941∙28201∙102461, 941∙44651∙4668511, 941∙209621∙1133641, 941∙322891∙701711, 941∙355321∙1732421
Carmichael numbers: 947∙29327∙1983763, 947∙47129∙299539, 947∙307451∙10398433
Carmichael numbers: 953∙2857∙9521, 953∙5881∙18257, 953∙17137∙69497, 953∙52361∙159937, 953∙159937∙2771273
Carmichael numbers: 967∙1289∙25439, 967∙1933∙4831, 967∙4831∙11593, 967∙26083∙5044453, 967∙62791∙7589863, 967∙88873∙1909783, 967∙156493∙30265747
Carmichael numbers: 971∙3881∙753691, 971∙8731∙44621, 971∙12611∙3061321, 971∙110581∙635351, 971∙142591∙2387171, 971∙169751∙648931, 971∙1324051∙3263081
Carmichael numbers: 977∙2441∙794953, 977∙5857∙12689, 977∙6833∙39041, 977∙17569∙41969, 977∙478241∙155747153
Carmichael numbers: 983∙3929∙8839, 983∙8839∙1241249, 983∙970217∙190744663
Carmichael numbers: 991∙4951∙58411, 991∙10111∙501001, 991∙16831∙26731, 991∙56431∙607861, 991∙99991∙5215321, 991∙118801∙206911, 991∙138403∙336997, 991∙167311∙312841, 991∙338581∙890011, 991∙658351∙1924561
Carmichael numbers: 997∙1993∙56773, 997∙8467∙367027, 997∙12451∙4137883, 997∙17929∙130477, 997∙29383∙450691, 997∙167329∙15166093, 997∙1002973∙99996409
 
for p = 2 to 61
──────── 1038 Carmichael numbers found.
carmichael3(p)
next
 
func carmichael3(p1)
if isprime(p1) = 0 return ok
for h3 = 1 to p1 -1
t1 = (h3 + p1) * (p1 -1)
t2 = (-p1 * p1) % h3
if t2 < 0
t2 = t2 + h3
ok
for d = 1 to h3 + p1 -1
if t1 % d = 0 and t2 = (d % h3)
p2 = 1 + (t1 / d)
if isprime(p2) = 0
loop
ok
p3 = 1 + floor((p1 * p2 / h3))
if isprime(p3) = 0 or ((p2 * p3) % (p1 -1)) != 1
loop
ok
see "" + p1 + " " + p2 + " " + p3 + " " + p1*p2*p3 + nl
ok
next
next
func isprime(num)
if (num <= 1) return 0 ok
if (num % 2 = 0) and num != 2
return 0
ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0)
return 0
ok
next
return 1
</syntaxhighlight>
Output:
<pre>
The following are Carmichael munbers for p1 <= 61:
p1 p2 p3 product
== == == =======
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
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
« { }
3 ROT '''FOR''' p1
2 p1 1 - '''FOR''' h3
1 h3 p1 + 1 - '''FOR''' d
'''IF''' h3 p1 + p1 1 - * d MOD NOT p1 SQ NEG h3 MOD d h3 MOD == AND '''THEN'''
p1 1 - h3 p1 + d IQUOT * 1 +
'''CASE'''
DUP ISPRIME? NOT '''THEN''' DROP '''END'''
p1 OVER * h3 IQUOT 1 +
DUP ISPRIME? NOT '''THEN''' DROP2 '''END'''
DUP2 * p1 1 - MOD 1 ≠ '''THEN''' DROP2 '''END'''
p1 UNROT 3 →LIST 1 →LIST +
'''END'''
'''END'''
'''NEXT'''
'''NEXT'''
p1 NEXTPRIME 1 - 'p1' STO
'''NEXT'''
» '<span style="color:blue">CARMIC</span>' STO
 
61 <span style="color:blue">CARMIC</span>
{{out}}
<pre>
1: { { 3 11 17 } { 5 29 73 } { 5 17 29 } { 5 13 17 } { 7 19 67 } { 7 31 73 } { 7 13 31 } { 7 73 103 } { 7 13 19 } { 13 61 397 } { 13 37 241 } { 13 97 421 } { 13 37 97 } { 13 37 61 } { 17 353 1201 } { 19 199 271 } { 23 199 353 } { 29 113 1093 } { 29 197 953 } { 31 991 15361 } { 31 61 631 } { 31 151 1171 } { 31 61 271 } { 31 61 211 } { 31 271 601 } { 31 181 331 } { 37 109 2017 } { 37 73 541 } { 37 613 1621 } { 37 73 181 } { 37 73 109 } { 41 1721 35281 } { 41 881 12041 } { 41 241 761 } { 41 241 521 } { 43 631 13567 } { 43 127 2731 } { 43 127 1093 } { 43 211 757 } { 43 631 1597 } { 43 127 211 } { 43 211 337 } { 43 547 673 } { 43 3361 3907 } { 47 3359 6073 } { 47 1151 1933 } { 47 3727 5153 } { 53 53 937 } { 53 157 2081 } { 53 157 521 } { 59 1451 2089 } { 61 421 12841 } { 61 181 5521 } { 61 61 1861 } { 61 61 1861 } { 61 181 1381 } { 61 541 3001 } { 61 661 2521 } { 61 241 421 } { 61 3361 4021 } }
</pre>
 
=={{header|Ruby}}==
{{works with|Ruby|1.9}}
<langsyntaxhighlight lang="ruby"># Generate Charmichael Numbers
 
require 'prime'
Line 1,556 ⟶ 3,333:
end
puts
end</langsyntaxhighlight>
 
{{out}}
Line 1,648 ⟶ 3,425:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">
fn is_prime(n: i64) -> bool {
if n > 1 {
Line 1,700 ⟶ 3,477:
.count(); // Evaluate entire iterator
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,715 ⟶ 3,492:
(61, 3361, 4021)
</pre>
 
=={{header|Seed7}}==
The function [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime] below is borrowed from the [http://seed7.sourceforge.net/algorith Seed7 algorithm collection].
 
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
Line 1,766 ⟶ 3,542:
end if;
end for;
end func;</langsyntaxhighlight>
 
{{out}}
Line 1,840 ⟶ 3,616:
61 * 3361 * 4021 = 824389441
</pre>
 
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">func forprimes(a, b, callback) {
<lang ruby>var ntheory = frequire('ntheory');
for (a = (a-1 -> next_prime); a <= b; a.next_prime!) {
callback(a)
}
}
 
ntheory.forprimes({3, |*61, func(p|) {
pfor =h3 in Number.new(2 ..^ p[-1]); {
range(2, var ph3 = (p-1).each {+ |h3|)
varfor ph3d =in (p1 +..^ h3ph3); {
range(1, ph3 ((-1p * p).each {% |h3) != (d| % h3) && next
((p-p1) * pph3) % h3) != (d % h3) && next;
var q = 1+((p-1) * ph3) %/ d && next;)
var q.is_prime = 1+((p-1) * ph3 /|| d);next
ntheory.is_primevar r = 1+((p*q) ||- next;1)/h3)
var r.is_prime = 1+((p*q -|| 1)/h3);next
ntheory.is_prime(q*r) % (p-1) == 1 || next;
printf(q*r)"%2d x %5d (p-1)x %5d == 1%s\n",p,q,r, || next;p*q*r)
printf("%2d x %5d x %5d = %s\n",p,q,r,ntheory.vecprod(p,q,r));
}
}
})</syntaxhighlight>
}, 3, 61);</lang>
 
{{out}}
Line 1,874 ⟶ 3,652:
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Swift}}==
 
{{trans|Rust}}
 
<syntaxhighlight lang="swift">import Foundation
 
extension BinaryInteger {
@inlinable
public var isPrime: Bool {
if self == 0 || self == 1 {
return false
} else if self == 2 {
return true
}
 
let max = Self(ceil((Double(self).squareRoot())))
 
for i in stride(from: 2, through: max, by: 1) {
if self % i == 0 {
return false
}
}
 
return true
}
}
 
@inlinable
public func carmichael<T: BinaryInteger & SignedNumeric>(p1: T) -> [(T, T, T)] {
func mod(_ n: T, _ m: T) -> T { (n % m + m) % m }
 
var res = [(T, T, T)]()
 
guard p1.isPrime else {
return res
}
 
for h3 in stride(from: 2, to: p1, by: 1) {
for d in stride(from: 1, to: h3 + p1, by: 1) {
if (h3 + p1) * (p1 - 1) % d != 0 || mod(-p1 * p1, h3) != d % h3 {
continue
}
 
let p2 = 1 + (p1 - 1) * (h3 + p1) / d
 
guard p2.isPrime else {
continue
}
 
let p3 = 1 + p1 * p2 / h3
 
guard p3.isPrime && (p2 * p3) % (p1 - 1) == 1 else {
continue
}
 
res.append((p1, p2, p3))
}
}
 
return res
}
 
 
let res =
(1..<62)
.lazy
.filter({ $0.isPrime })
.map(carmichael)
.filter({ !$0.isEmpty })
.flatMap({ $0 })
 
for c in res {
print(c)
}</syntaxhighlight>
 
{{out}}
 
<pre>(3, 11, 17)
(5, 29, 73)
(5, 17, 29)
(5, 13, 17)
(7, 19, 67)
...
(61, 661, 2521)
(61, 271, 571)
(61, 241, 421)
(61, 3361, 4021)</pre>
=={{header|Tcl}}==
Using the primality tester from [[Miller-Rabin primality test#Tcl|the Miller-Rabin task]]...
<langsyntaxhighlight lang="tcl">proc carmichael {limit {rounds 10}} {
set carmichaels {}
for {set p1 2} {$p1 <= $limit} {incr p1} {
Line 1,899 ⟶ 3,763:
}
return $carmichaels
}</langsyntaxhighlight>
Demonstrating:
<langsyntaxhighlight lang="tcl">set results [carmichael 61 2]
puts "[expr {[llength $results]/4}] Carmichael numbers found"
foreach {p1 p2 p3 c} $results {
puts "$p1 x $p2 x $p3 = $c"
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,978 ⟶ 3,842:
61 x 241 x 421 = 6189121
61 x 3361 x 4021 = 824389441
</pre>
=={{header|Vala}}==
{{trans|D}}
<syntaxhighlight lang="vala">long mod(long n, long m) {
return ((n % m) + m) % m;
}
 
bool is_prime(long n) {
if (n == 2 || n == 3)
return true;
else if (n < 2 || n % 2 == 0 || n % 3 == 0)
return false;
for (long div = 5, inc = 2; div * div <= n;
div += inc, inc = 6 - inc)
if (n % div == 0)
return false;
return true;
}
 
void main() {
for (long p = 2; p <= 63; p++) {
if (!is_prime(p)) continue;
for (long h3 = 2; h3 <= p; h3++) {
var g = h3 + p;
for (long d = 1; d <= g; d++) {
if ((g * (p - 1)) % d != 0 || mod(-p * p, h3) != d % h3)
continue;
var q = 1 + (p - 1) * g / d;
if (!is_prime(q)) continue;
var r = 1 + (p * q / h3);
if (!is_prime(r) || (q * r) % (p - 1) != 1) continue;
stdout.printf("%5ld × %5ld × %5ld = %10ld\n", p, q, r, p * q * r);
}
}
}
}</syntaxhighlight>
{{out}}
<pre>
3 × 11 × 17 = 561
3 × 3 × 5 = 45
5 × 29 × 73 = 10585
5 × 5 × 13 = 325
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 × 7 × 13 = 637
7 × 73 × 103 = 52633
7 × 13 × 19 = 1729
11 × 11 × 61 = 7381
11 × 11 × 41 = 4961
11 × 11 × 31 = 3751
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 × 17 × 97 = 28033
17 × 353 × 1201 = 7207201
19 × 43 × 409 = 334153
19 × 19 × 181 = 65341
19 × 19 × 73 = 26353
19 × 19 × 37 = 13357
19 × 199 × 271 = 1024651
23 × 23 × 89 = 47081
23 × 23 × 67 = 35443
23 × 199 × 353 = 1615681
29 × 29 × 421 = 354061
29 × 113 × 1093 = 3581761
29 × 29 × 281 = 236321
29 × 197 × 953 = 5444489
31 × 991 × 15361 = 471905281
31 × 61 × 631 = 1193221
31 × 151 × 1171 = 5481451
31 × 31 × 241 = 231601
31 × 61 × 271 = 512461
31 × 61 × 211 = 399001
31 × 271 × 601 = 5049001
31 × 31 × 61 = 58621
31 × 181 × 331 = 1857241
37 × 109 × 2017 = 8134561
37 × 73 × 541 = 1461241
37 × 613 × 1621 = 36765901
37 × 73 × 181 = 488881
37 × 37 × 73 = 99937
37 × 73 × 109 = 294409
41 × 1721 × 35281 = 2489462641
41 × 881 × 12041 = 434932961
41 × 41 × 281 = 472361
41 × 41 × 241 = 405121
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 × 43 × 463 = 856087
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 × 47 × 277 = 611893
47 × 47 × 139 = 307051
47 × 3359 × 6073 = 958762729
47 × 1151 × 1933 = 104569501
47 × 3727 × 5153 = 902645857
53 × 53 × 937 = 2632033
53 × 157 × 2081 = 17316001
53 × 79 × 599 = 2508013
53 × 53 × 313 = 879217
53 × 157 × 521 = 4335241
53 × 53 × 157 = 441013
59 × 59 × 1741 = 6060421
59 × 59 × 349 = 1214869
59 × 59 × 233 = 811073
59 × 1451 × 2089 = 178837201
61 × 421 × 12841 = 329769721
61 × 181 × 5521 = 60957361
61 × 61 × 1861 = 6924781
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
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
 
var mod = Fn.new { |n, m| ((n%m) + m) % m }
 
var carmichael = Fn.new { |p1|
for (h3 in 2...p1) {
for (d in 1...h3 + p1) {
if ((h3 + p1) * (p1 - 1) % d == 0 && mod.call(-p1 * p1, h3) == d % h3) {
var p2 = 1 + ((p1 - 1) * (h3 + p1) / d).floor
if (Int.isPrime(p2)) {
var p3 = 1 + (p1 * p2 / h3).floor
if (Int.isPrime(p3)) {
if (p2 * p3 % (p1 - 1) == 1) {
var c = p1 * p2 * p3
Fmt.print("$2d $4d $5d $10d", p1, p2, p3, c)
}
}
}
}
}
}
}
 
System.print("The following are Carmichael munbers for p1 <= 61:\n")
System.print("p1 p2 p3 product")
System.print("== == == =======")
for (p1 in 2..61) {
if (Int.isPrime(p1)) carmichael.call(p1)
}</syntaxhighlight>
 
{{out}}
<pre>
The following are Carmichael munbers for p1 <= 61:
 
p1 p2 p3 product
== == == =======
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
</pre>
 
=={{header|zkl}}==
Using the Miller-Rabin primality test in lib GMP.
<langsyntaxhighlight lang="zkl">var BN=Import("zklBigNum"), bi=BN(0); // gonna recycle bi
primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61);
var p2,p3;
Line 1,993 ⟶ 4,104:
{ T(p1,p2,p3) } // return list of three primes in Carmichael number
]];
fcn mod(a,b) { m:=a%b; if(m<0) m+b else m }</langsyntaxhighlight>
<syntaxhighlight lang="zkl">cs.len().println(" Carmichael numbers found:");
cs.pump(Console.println,fcn([(p1,p2,p3)]){
"%2d * %4d * %5d = %d".fmt(p1,p2,p3,p1*p2*p3) });</langsyntaxhighlight>
{{out}}
<pre>
Line 2,013 ⟶ 4,124:
61 * 3361 * 4021 = 824389441
</pre>
 
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<lang zxbasic>10 FOR p=2 TO 61
20 LET n=p: GO SUB 1000
30 IF NOT n THEN GO TO 200
40 FOR h=1 TO p-1
50 FOR d=1 TO h-1+p
60 IF NOT (FN m((h+p)*(p-1),d)=0 AND FN w(-p*p,h)=FN m(d,h)) THEN GO TO 180
70 LET q=INT (1+((p-1)*(h+p)/d))
80 LET n=q: GO SUB 1000
90 IF NOT n THEN GO TO 180
100 LET r=INT (1+(p*q/h))
110 LET n=r: GO SUB 1000
120 IF (NOT n) OR ((FN m((q*r),(p-1))<>1)) THEN GO TO 180
130 PRINT p;" ";q;" ";r
180 NEXT d
190 NEXT h
200 NEXT p
210 STOP
1000 IF n<4 THEN LET n=(n>1): RETURN
1010 IF (NOT FN m(n,2)) OR (NOT FN m(n,3)) THEN LET n=0: RETURN
1020 LET i=5
1030 IF NOT ((i*i)<=n) THEN LET n=1: RETURN
1040 IF (NOT FN m(n,i)) OR NOT FN m(n,(i+2)) THEN LET n=0: RETURN
1050 LET i=i+6
1060 GO TO 1030
2000 DEF FN m(a,b)=a-(INT (a/b)*b): REM Mod function
2010 DEF FN w(a,b)=FN m(FN m(a,b)+b,b): REM Mod function modified
</lang>
Aerobar
1,151

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/222733...351872"