Carmichael 3 strong pseudoprimes: Difference between revisions

← Older edit

Carmichael 3 strong pseudoprimes (view source)

Revision as of 09:19, 13 November 2023

47,941 bytes added , 6 months ago

m

→‎{{header|RPL}}: tweaked the code

Aerobar

1,150

edits

Revision as of 02:39, 6 January 2019 (view source) Alextretyak (talk \| contribs) (Added 11l) ← Older edit		Latest revision as of 09:19, 13 November 2023 (view source) Aerobar (talk \| contribs) m (→‎{{header\|RPL}}: tweaked the code)
(33 intermediate revisions by 20 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 30: <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}} <~~lang~~syntaxhighlight lang="11l">F mod_(n, m) R ((n % m) + m) % m Line 64 ⟶ 66: I !is_prime(r) \| (q * r) % (p - 1) != 1 L.continue print(p‘ x ’q‘ x ’r)</~~lang~~syntaxhighlight> {{out}} <pre> Line 85 ⟶ 87: 61 x 3361 x 4021 </pre> =={{header\|Ada}}== Uses the Miller_Rabin package from [[Miller-Rabin primality test#ordinary integers]]. <~~lang~~syntaxhighlight ~~Ada~~lang="ada">with Ada.Text_IO, Miller_Rabin; procedure Nemesis is Line 130 ⟶ 131: end if; end loop; end Nemesis;</~~lang~~syntaxhighlight> {{out}} Line 144 ⟶ 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). <~~lang~~syntaxhighlight lang="algol68"># sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise # PROC sieve = ( REF[]BOOL s )VOID: BEGIN Line 179: IF is prime[ prime3 ] THEN IF ( prime2 * prime3 ) MOD ( prime1 - 1 ) = 1 THEN print( ( whole( prime1, 0 ), " ", whole( prime2, 0 ), " ", whole( prime3, 0 )~~, newline~~ ) ); print( ( newline ) ) FI FI Line 187 ⟶ 188: OD FI OD</~~lang~~syntaxhighlight> {{out}} <pre> Line 218 ⟶ 219: 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 gp-1 d -> zero? mod d+pp h3 [ q: 1 + ((p-1)g)/d if prime? q [ r: 1 + (p q) / h3 if and? [prime? r] [one? (qr) % p-1]-> printOneLine p q r (pqr) ] ] ]</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(-p1p1,h3) == d%h3) { p2 = int(1+((p1-1)(h3+p1)/d)) if (!is_prime(p2)) { continue } p3 = int(1+(p1p2/h3)) if (!is_prime(p3) \|\| (p2p3)%(p1-1) != 1) { continue } printf("%5d x %5d x %5d = %10d\n",p1,p2,p3,p1p2p3) 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; ii<=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 = (-p1p1) 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(p1p2/h3) 240 if isprime(p3) = 0 or ((p2p3) 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 = ii to max_sieve step i2 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(-pp,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+(pq/h)) 110 LET n=r: GO SUB 1000 120 IF (NOT n) OR ((FN m((qr),(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 ((ii)<=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 269 ⟶ 855: return 0; } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 288 ⟶ 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}}== <~~lang~~syntaxhighlight lang="lisp"> (ns example (:gen-class)) Line 318 ⟶ 1,031: (doseq [t numbers] (println (format "%5d x %5d x %5d = %10d" (first t) (second t) (last t) (apply * t)))) </syntaxhighlight> ~~</lang>~~ {{Out}} <pre> Line 394 ⟶ 1,107: </pre> =={{header\|D}}== <~~lang~~syntaxhighlight 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 426 ⟶ 1,139: } } }</~~lang~~syntaxhighlight> {{out}} <pre>3 x 11 x 17 Line 497 ⟶ 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}}== <~~lang~~syntaxhighlight 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 514 ⟶ 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}} <~~lang~~syntaxhighlight lang="scheme"> (charms 3) 💥 561 = 3 x 11 x 17 Line 539 ⟶ 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#)] <~~lang~~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)} Line 552 ⟶ 1,299: 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 (P1P2)))) </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 625 ⟶ 1,372: 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, INTEGER8 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... <~~lang~~syntaxhighlight ~~Fortran~~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. Line 669 ⟶ 1,512: END IF END DO END</~~lang~~syntaxhighlight> ===Output=== Line 745 ⟶ 1,588: 61 3361 4021 824389441 </pre> ~~=={{header\|FreeBASIC}}==~~ ~~<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</lang>~~ ~~{{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\|Go}}== <~~lang~~syntaxhighlight lang="go">package main import "fmt" Line 925 ⟶ 1,637: if isPrime(p1) { carmichael(p1) } } }</~~lang~~syntaxhighlight> {{out}} Line 1,003 ⟶ 1,715: 61 3361 4021 824389441 </pre> =={{header\|Haskell}}== {{trans\|Ruby}} Line 1,009 ⟶ 1,720: {{Works with\|GHC\|7.4.1}} {{Works with\|primes\|0.2.1.0}} <~~lang~~syntaxhighlight lang="haskell">#!/usr/bin/runhaskell import Data.Numbers.Primes Line 1,026 ⟶ 1,737: return (p, q, r) main = putStr $ unlines $ map show carmichaels</~~lang~~syntaxhighlight> {{out}} <pre> Line 1,099 ⟶ 1,810: (61,3361,4021) </pre> =={{header\|Icon}} and {{header\|Unicon}}== The following works in both languages. <~~lang~~syntaxhighlight lang="unicon">link "factors" procedure main(A) Line 1,126 ⟶ 1,836: procedure format(p1,p2,p3) return left(p1\|\|" * "\|\|p2\|\|" * "\|\|p3,20)\|\|" = "\|\|(p1p2p3) end</~~lang~~syntaxhighlight> Output, with middle lines elided: Line 1,160 ⟶ 1,870: -> </pre> =={{header\|J}}== <syntaxhighlight lang="j"> ~~<lang J>~~ q =: (,"0 1~ >:@i.@<:@+/"1)&.>@(,&.>"0 1~ >:@i.)&.>@I.@(1&p:@i.)@>: f1 =: (0: = {. \| <:@{: * 1&{ + {:) . ((1&{ \| -@:@{:) = 1&{ \| {.) Line 1,169 ⟶ 1,878: p3 =: 3:$0:`((* 1&p:)@({: , {. , (<.@>:@(1&{ %~ {. * {:))))@.(@{.)@(p2 , }.) (-. 3:$0:)@((("0 f2)@p3"1)@;@;@q) 61 </syntaxhighlight> ~~</lang>~~ Output <pre> Line 1,242 ⟶ 1,951: 61 3361 4021 </pre> =={{header\|Java}}== {{trans\|D}} <~~lang~~syntaxhighlight lang="java">public class Test { static int mod(int n, int m) { Line 1,283 ⟶ 1,991: } } }</~~lang~~syntaxhighlight> <pre>3 x 11 x 17 5 x 29 x 73 Line 1,353 ⟶ 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''' <~~lang~~syntaxhighlight lang="julia">using Primes function carmichael(pmax::Integer) Line 1,378 ⟶ 2,085: end return reshape(car, 3, length(car) ÷ 3) end</~~lang~~syntaxhighlight> '''Main''' <~~lang~~syntaxhighlight lang="julia">hi = 61 car = carmichael(hi) Line 1,402 ⟶ 2,109: @printf("p× %d × %d = %d ", q, r, c) end println("\n\n", size(car)[2], " results in total.")</~~lang~~syntaxhighlight> {{out}} Line 1,449 ⟶ 2,156: 42 results in total.</pre> =={{header\|Kotlin}}== {{trans\|D}} <~~lang~~syntaxhighlight lang="scala">fun Int.isPrime(): Boolean { return when { this == 2 -> true Line 1,487 ⟶ 2,193: } } }</~~lang~~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.pv.qv.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}}== <~~lang~~syntaxhighlight 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 1,499 ⟶ 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]]</~~lang~~syntaxhighlight> =={{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}}== <~~lang~~syntaxhighlight lang="parigp">f(p)={ my(v=List(),q,r); for(h=2,p-1, Line 1,513 ⟶ 2,435: Set(v) }; forprime(p=3,67,v=f(p); for(i=1,#v,print1(v[i]", ")))</~~lang~~syntaxhighlight> {{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}} <~~lang~~syntaxhighlight lang="perl">use ntheory qw/forprimes is_prime vecprod/; forprimes { my $p = $_; Line 1,535 ⟶ 2,456: } } } 3,61;</~~lang~~syntaxhighlight> {{out}} <pre> Line 1,548 ⟶ 2,469: 61 x 3361 x 4021 = 824389441 </pre> ~~=={{header\|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. (Perl 6 uses arbitrary precision in any case.)~~ ~~<lang perl6>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}";~~ } } } ~~}</lang>~~ ~~{{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\|Phix}}== <!--<syntaxhighlight lang="phix">(phixonline)--> ~~Uses is_prime() from [[Extensible_prime_generator#Phix\|Extensible_prime_generator]]~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~<lang Phix>integer count = 0~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> ~~for p1=1 to 61 do~~ <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> ~~if is_prime(p1) then~~ <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 h3=1 to p1 do~~ <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> ~~atom h3p1 = h3 + p1~~ <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 d=1 to h3p1-1 do~~ <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 mod(h3p1(p1-1),d)=0~~ <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> ~~and mod(-(p1p1),h3) = mod(d,h3) then~~ <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> ~~atom p2 := 1 + floor(((p1-1)h3p1)/d),~~ <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> ~~p3 := 1 +floor(p1p2/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> ~~if is_prime(p2)~~ <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> ~~and is_prime(p3)~~ <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> ~~and mod(p2p3,p1-1)=1 then~~ <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> ~~if count<5 or count>55 then~~ <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> ~~printf(1,"%d * %d * %d = %d\n",{p1,p2,p3,p1p2p3})~~ <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> ~~elsif count=35 then puts(1,"...\n") end if~~ <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> ~~count += 1~~ <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~end if~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end for~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~end for~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~end if~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end for~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~printf(1,"%d Carmichael numbers found\n",count)</lang>~~ <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> Line 1,680 ⟶ 2,510: 69 Carmichael numbers found </pre> =={{header\|PicoLisp}}== <~~lang~~syntaxhighlight ~~PicoLisp~~lang="picolisp">(de modulo (X Y) (% (+ Y (% X Y)) Y) ) Line 1,721 ⟶ 2,550: (prinl) (bye)</~~lang~~syntaxhighlight> =={{header\|PL/I}}== <~~lang~~syntaxhighlight PLlang="pl/Ii">Carmichael: procedure options (main, reorder); /* 24 January 2014 / declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31); Line 1,750 ⟶ 2,578: / Uses is_prime from Rosetta Code PL/I. / end Carmichael;</~~lang~~syntaxhighlight> Results: <pre> Line 1,847 ⟶ 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, -P1P1 mod H3 =:= D mod H3, P2 is 1 + (P1 - 1)(H3 + P1) div D, prime(P2), P3 is 1 + P1P2 div H3, prime(P3), X is P1P2P3. 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, _) :- DD > 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}}== <~~lang~~syntaxhighlight lang="python">class Isprime(): ''' Extensible sieve of Eratosthenes Line 1,919 ⟶ 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)))</~~lang~~syntaxhighlight> {{out}} <pre>(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19), Line 1,935 ⟶ 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}}== <~~lang~~syntaxhighlight lang="racket"> #lang racket (require math) Line 1,954 ⟶ 2,930: (displayln (list p1 p2 p3 '=> (* p1 p2 p3)))))) (next (+ d 1)))))) </syntaxhighlight> ~~</lang>~~ Output: <~~lang~~syntaxhighlight lang="racket"> (3 11 17 => 561) (5 29 73 => 10585) Line 2,019 ⟶ 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}}== Note that REXX's version of   '''modulus'''   (<big><code>'''//'''</code></big>)   is really a   ''remainder''   function. Line 2,027 ⟶ 3,094: Some code optimization was done, while not necessary for the small default number ('''61'''),   it was significant for larger numbers. <~~lang~~syntaxhighlight 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./ Line 2,068 ⟶ 3,135: if x//(k+2) ==0 then return 0 end /k/ @.x=1; return 1</~~lang~~syntaxhighlight> '''output'''   when using the default input: <pre> Line 2,098 ⟶ 3,165: ──────── 8716 Carmichael numbers found. </pre> =={{header\|Ring}}== <~~lang~~syntaxhighlight lang="ring"> # Project : Carmichael 3 strong pseudoprimes Line 2,144 ⟶ 3,210: next return 1 </syntaxhighlight> ~~</lang>~~ Output: <pre> Line 2,219 ⟶ 3,285: 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}} <~~lang~~syntaxhighlight lang="ruby"># Generate Charmichael Numbers require 'prime' Line 2,240 ⟶ 3,333: end puts end</~~lang~~syntaxhighlight> {{out}} Line 2,332 ⟶ 3,425: =={{header\|Rust}}== <~~lang~~syntaxhighlight lang="rust"> fn is_prime(n: i64) -> bool { if n > 1 { Line 2,384 ⟶ 3,477: .count(); // Evaluate entire iterator } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 2,399 ⟶ 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]. <~~lang~~syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; const func boolean: isPrime (in integer: number) is func Line 2,450 ⟶ 3,542: end if; end for; end func;</~~lang~~syntaxhighlight> {{out}} Line 2,524 ⟶ 3,616: 61 * 3361 * 4021 = 824389441 </pre> =={{header\|Sidef}}== {{trans\|Perl}} <~~lang~~syntaxhighlight lang="ruby">func forprimes(a, b, callback) { for (a = (a-1 -> next_prime); a <= b; a.next_prime!) { callback(a) Line 2,547 ⟶ 3,638: } } })</~~lang~~syntaxhighlight> {{out}} Line 2,561 ⟶ 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]]... <~~lang~~syntaxhighlight lang="tcl">proc carmichael {limit {rounds 10}} { set carmichaels {} for {set p1 2} {$p1 <= $limit} {incr p1} { Line 2,586 ⟶ 3,763: } return $carmichaels }</~~lang~~syntaxhighlight> Demonstrating: <~~lang~~syntaxhighlight 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" }</~~lang~~syntaxhighlight> {{out}} <pre> Line 2,665 ⟶ 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. <~~lang~~syntaxhighlight 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 2,680 ⟶ 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 }</~~lang~~syntaxhighlight> <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,p1p2p3) });</~~lang~~syntaxhighlight> {{out}} <pre> Line 2,700 ⟶ 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(-pp,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+(pq/h))~~ ~~110 LET n=r: GO SUB 1000~~ ~~120 IF (NOT n) OR ((FN m((qr),(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 ((ii)<=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>~~