Carmichael 3 strong pseudoprimes: Difference between revisions
m (→vertical list: changed the format of the output.) |
m (fixed version headers for REXX.) |
||
Line 1,184:
=={{header|REXX}}==
===vertical list===
Note that REXX's version of '''modulus''' (<big><code>'''//'''</code></big>) is really a ''remainder'' function.
Line 1,315:
</pre>
===horizontal list===
This REXX version (pre-)generates a number of primes to assist the '''isPrime''' function.
<lang rexx>/*REXX program calculates Carmichael 3─strong pseudoprimes (up to and including N). */
|
Revision as of 03:03, 30 June 2016
You are encouraged to solve this task according to the task description, using any language you may know.
A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it.
The Miller Rabin Test uses a combination of Fermat's Little Theorem and Chinese Division Theorem to overcome this.
The purpose of this task is to investigate such numbers using a method based on Carmichael numbers, as suggested in Notes by G.J.O Jameson March 2010.
Task:
Find Carmichael numbers of the form:
where () for all up to 61.
(See page 7 of Notes by G.J.O Jameson March 2010 for solutions.)
- Pseudocode
For a given
for 1 < h3 < Prime1
- for 0 < d < h3+Prime1
- if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3
- then
- Prime2 = 1 + ((Prime1-1) * (h3+Prime1)/d)
- next d if Prime2 is not prime
- Prime3 = 1 + (Prime1*Prime2/h3)
- next d if Prime3 is not prime
- next d if (Prime2*Prime3) mod (Prime1-1) not equal 1
- Prime1 * Prime2 * Prime3 is a Carmichael Number
Ada
Uses the Miller_Rabin package from Miller-Rabin primality test#ordinary integers. <lang Ada>with Ada.Text_IO, Miller_Rabin;
procedure Nemesis is
type Number is range 0 .. 2**40-1; -- sufficiently large for the task
function Is_Prime(N: Number) return Boolean is package MR is new Miller_Rabin(Number); use MR; begin return MR.Is_Prime(N) = Probably_Prime; end Is_Prime;
begin
for P1 in Number(2) .. 61 loop if Is_Prime(P1) then for H3 in Number(1) .. P1 loop declare G: Number := H3 + P1; P2, P3: Number; begin Inner: for D in 1 .. G-1 loop if ((H3+P1) * (P1-1)) mod D = 0 and then (-(P1 * P1)) mod H3 = D mod H3 then P2 := 1 + ((P1-1) * G / D); P3 := 1 +(P1*P2/H3); if Is_Prime(P2) and then Is_Prime(P3) and then (P2*P3) mod (P1-1) = 1 then Ada.Text_IO.Put_Line ( Number'Image(P1) & " *" & Number'Image(P2) & " *" & Number'Image(P3) & " = " & Number'Image(P1*P2*P3) ); end if; end if; end loop Inner; end; end loop; end if; end loop;
end Nemesis;</lang>
- Output:
3 * 11 * 17 = 561 5 * 29 * 73 = 10585 5 * 17 * 29 = 2465 5 * 13 * 17 = 1105 7 * 19 * 67 = 8911 ... (the full output is 69 lines long) ... 61 * 271 * 571 = 9439201 61 * 241 * 421 = 6189121 61 * 3361 * 4021 = 824389441
C
<lang C>
- include <stdio.h>
/* C's % operator actually calculates the remainder of a / b so we need a
* small adjustment so it works as expected for negative values */
- define mod(n,m) ((((n) % (m)) + (m)) % (m))
int is_prime(unsigned int n) {
if (n <= 3) { return n > 1; } else if (!(n % 2) || !(n % 3)) { return 0; } else { unsigned int i; for (i = 5; i*i <= n; i += 6) if (!(n % i) || !(n % (i + 2))) return 0; return 1; }
}
void carmichael3(int p1) {
if (!is_prime(p1)) return;
int h3, d, p2, p3; 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 = 1 + ((p1 - 1) * (h3 + p1)/d); if (!is_prime(p2)) continue; p3 = 1 + (p1 * p2 / h3); if (!is_prime(p3) || (p2 * p3) % (p1 - 1) != 1) continue; printf("%d %d %d\n", p1, p2, p3); } } }
}
int main(void) {
int p1; for (p1 = 2; p1 < 62; ++p1) carmichael3(p1); return 0;
} </lang>
- Output:
3 11 17 5 29 73 5 17 29 5 13 17 7 19 67 7 31 73 . . . 61 181 1381 61 541 3001 61 661 2521 61 271 571 61 241 421 61 3361 4021
D
<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 {
if (n == 2 || n == 3) return true; else if (n < 2 || n % 2 == 0 || n % 3 == 0) return false; for (uint div = 5, inc = 2; div ^^ 2 <= n; div += inc, inc = 6 - inc) if (n % div == 0) return false; return true;
}
void main() {
import std.stdio;
foreach (immutable p; 2 .. 62) { if (!p.isPrime) continue; foreach (immutable h3; 2 .. p) { immutable g = h3 + p; foreach (immutable d; 1 .. g) { if ((g * (p - 1)) % d != 0 || mod(-p * p, h3) != d % h3) continue; immutable q = 1 + (p - 1) * g / d; if (!q.isPrime) continue; immutable r = 1 + (p * q / h3); if (!r.isPrime || (q * r) % (p - 1) != 1) continue; writeln(p, " x ", q, " x ", r); } } }
}</lang>
- Output:
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 7 x 73 x 103 7 x 13 x 19 13 x 61 x 397 13 x 37 x 241 13 x 97 x 421 13 x 37 x 97 13 x 37 x 61 17 x 41 x 233 17 x 353 x 1201 19 x 43 x 409 19 x 199 x 271 23 x 199 x 353 29 x 113 x 1093 29 x 197 x 953 31 x 991 x 15361 31 x 61 x 631 31 x 151 x 1171 31 x 61 x 271 31 x 61 x 211 31 x 271 x 601 31 x 181 x 331 37 x 109 x 2017 37 x 73 x 541 37 x 613 x 1621 37 x 73 x 181 37 x 73 x 109 41 x 1721 x 35281 41 x 881 x 12041 41 x 101 x 461 41 x 241 x 761 41 x 241 x 521 41 x 73 x 137 41 x 61 x 101 43 x 631 x 13567 43 x 271 x 5827 43 x 127 x 2731 43 x 127 x 1093 43 x 211 x 757 43 x 631 x 1597 43 x 127 x 211 43 x 211 x 337 43 x 433 x 643 43 x 547 x 673 43 x 3361 x 3907 47 x 3359 x 6073 47 x 1151 x 1933 47 x 3727 x 5153 53 x 157 x 2081 53 x 79 x 599 53 x 157 x 521 59 x 1451 x 2089 61 x 421 x 12841 61 x 181 x 5521 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
EchoLisp
<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)) (for* ((Prime1 (primes N))
(h3 (in-range 1 Prime1)) (d (+ h3 Prime1))) (set! h31 (+ h3 Prime1)) #:continue (!zero? (modulo (* h31 (1- Prime1)) d)) #:continue (!= (modulo d h3) (modulo (- (* Prime1 Prime1)) h3)) (set! Prime2 (1+ ( * (1- Prime1) (quotient h31 d)))) #:when (prime? Prime2) (set! Prime3 (1+ (quotient (* Prime1 Prime2) h3))) #:when (prime? Prime3) #:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1))) (printf " 💥 %12d = %d x %d x %d" (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))
</lang>
- Output:
<lang scheme> (charms 3) 💥 561 = 3 x 11 x 17 💥 10585 = 5 x 29 x 73 💥 2465 = 5 x 17 x 29 💥 1105 = 5 x 13 x 17
(charms 18)
- skipped ....
💥 902645857 = 47 x 3727 x 5153 💥 2632033 = 53 x 53 x 937 💥 17316001 = 53 x 157 x 2081 💥 4335241 = 53 x 157 x 521 💥 178837201 = 59 x 1451 x 2089 💥 329769721 = 61 x 421 x 12841 💥 60957361 = 61 x 181 x 5521 💥 6924781 = 61 x 61 x 1861 💥 6924781 = 61 x 61 x 1861 💥 15247621 = 61 x 181 x 1381 💥 99036001 = 61 x 541 x 3001 💥 101649241 = 61 x 661 x 2521 💥 6189121 = 61 x 241 x 421 💥 824389441 = 61 x 3361 x 4021 </lang>
Haskell
<lang haskell>#!/usr/bin/runhaskell
import Data.Numbers.Primes import Control.Monad (guard)
carmichaels = do
p <- takeWhile (<= 61) primes h3 <- [2..(p-1)] let g = h3 + p d <- [1..(g-1)] guard $ (g * (p - 1)) `mod` d == 0 && (-1 * p * p) `mod` h3 == d `mod` h3 let q = 1 + (((p - 1) * g) `div` d) guard $ isPrime q let r = 1 + ((p * q) `div` h3) guard $ isPrime r && (q * r) `mod` (p - 1) == 1 return (p, q, r)
main = putStr $ unlines $ map show carmichaels</lang>
- Output:
(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)
Icon and Unicon
The following works in both languages. <lang unicon>link "factors"
procedure main(A)
n := integer(!A) | 61 every write(carmichael3(!n))
end
procedure carmichael3(p1)
every (isprime(p1), (h := 1+!(p1-1)), (d := !(h+p1-1))) do if (mod(((h+p1)*(p1-1)),d) = 0, mod((-p1*p1),h) = mod(d,h)) then { p2 := 1 + (p1-1)*(h+p1)/d p3 := 1 + p1*p2/h if (isprime(p2), isprime(p3), mod((p2*p3),(p1-1)) = 1) then suspend format(p1,p2,p3) }
end
procedure mod(n,d)
return (d+n%d)%d
end
procedure format(p1,p2,p3)
return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)
end</lang>
Output, with middle lines elided:
->c3sp 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 ... 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 ->
Java
<lang java>public class Test {
static int mod(int n, int m) { return ((n % m) + m) % m; }
static boolean isPrime(int n) { if (n == 2 || n == 3) return true; else if (n < 2 || n % 2 == 0 || n % 3 == 0) return false; for (int div = 5, inc = 2; Math.pow(div, 2) <= n; div += inc, inc = 6 - inc) if (n % div == 0) return false; return true; }
public static void main(String[] args) { for (int p = 2; p < 62; p++) { if (!isPrime(p)) continue; for (int h3 = 2; h3 < p; h3++) { int g = h3 + p; for (int d = 1; d < g; d++) { if ((g * (p - 1)) % d != 0 || mod(-p * p, h3) != d % h3) continue; int q = 1 + (p - 1) * g / d; if (!isPrime(q)) continue; int r = 1 + (p * q / h3); if (!isPrime(r) || (q * r) % (p - 1) != 1) continue; System.out.printf("%d x %d x %d%n", p, q, r); } } } }
}</lang>
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 7 x 73 x 103 7 x 13 x 19 13 x 61 x 397 13 x 37 x 241 13 x 97 x 421 13 x 37 x 97 13 x 37 x 61 17 x 41 x 233 17 x 353 x 1201 19 x 43 x 409 19 x 199 x 271 23 x 199 x 353 29 x 113 x 1093 29 x 197 x 953 31 x 991 x 15361 31 x 61 x 631 31 x 151 x 1171 31 x 61 x 271 31 x 61 x 211 31 x 271 x 601 31 x 181 x 331 37 x 109 x 2017 37 x 73 x 541 37 x 613 x 1621 37 x 73 x 181 37 x 73 x 109 41 x 1721 x 35281 41 x 881 x 12041 41 x 101 x 461 41 x 241 x 761 41 x 241 x 521 41 x 73 x 137 41 x 61 x 101 43 x 631 x 13567 43 x 271 x 5827 43 x 127 x 2731 43 x 127 x 1093 43 x 211 x 757 43 x 631 x 1597 43 x 127 x 211 43 x 211 x 337 43 x 433 x 643 43 x 547 x 673 43 x 3361 x 3907 47 x 3359 x 6073 47 x 1151 x 1933 47 x 3727 x 5153 53 x 157 x 2081 53 x 79 x 599 53 x 157 x 521 59 x 1451 x 2089 61 x 421 x 12841 61 x 181 x 5521 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
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 carmichael function.
Function <lang Julia> function carmichael{T<:Integer}(pmax::T)
0 < pmax || throw(DomainError()) car = T[] 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) m%Δ==0 && Δ%h₃==pmh || continue q = div(m, Δ) + 1 isprime(q) || continue r = div((p*q - 1), h₃) + 1 isprime(r) && mod(q*r, (p-1))==1 || continue append!(car, [p, q, r]) end end end reshape(car, 3, div(length(car), 3))
end </lang>
Main <lang Julia> hi = 61 car = carmichael(hi)
curp = 0 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(@sprintf("\n\np = %d\n ", p)) tcnt = 0 end if tcnt == 4 print("\n ") tcnt = 1 else tcnt += 1 end print(@sprintf("p\u00d7%d\u00d7%d = %d ", q, r, c))
end println("\n\n", size(car)[2], " results in total.") </lang>
- Output:
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 = 13 p×37×61 = 29341 p×37×97 = 46657 p×37×241 = 115921 p×61×397 = 314821 p×97×421 = 530881 p = 17 p×41×233 = 162401 p×353×1201 = 7207201 p = 19 p×43×409 = 334153 p×199×271 = 1024651 p = 23 p×199×353 = 1615681 p = 29 p×113×1093 = 3581761 p×197×953 = 5444489 p = 31 p×61×211 = 399001 p×61×271 = 512461 p×61×631 = 1193221 p×151×1171 = 5481451 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×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×127×211 = 1152271 p×127×1093 = 5968873 p×127×2731 = 14913991 p×211×337 = 3057601 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×1151×1933 = 104569501 p×3359×6073 = 958762729 p×3727×5153 = 902645857 p = 53 p×79×599 = 2508013 p×157×521 = 4335241 p×157×2081 = 17316001 p = 59 p×1451×2089 = 178837201 p = 61 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 69 results in total.
Mathematica / Wolfram Language
<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_} /; PrimeQ[1 + (p1 - 1) (h3 + p1)/d] && Divisible[p1^2 + d, h3] :> {p1, 1 + (p1 - 1) (h3 + p1)/d, h3}, 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>
PARI/GP
<lang parigp>f(p)={
my(v=List(),q,r); for(h=2,p-1, for(d=1,h+p-1, if((h+p)*(p-1)%d==0 && Mod(p,h)^2==-d && isprime(q=(p-1)*(h+p)/d+1) && isprime(r=p*q\h+1)&&q*r%(p-1)==1, listput(v,p*q*r) ) ) ); Set(v)
}; forprime(p=3,67,v=f(p); for(i=1,#v,print1(v[i]", ")))</lang>
- Output:
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,
Perl
<lang perl>use ntheory qw/forprimes is_prime vecprod/;
forprimes { my $p = $_;
for my $h3 (2 .. $p-1) { my $ph3 = $p + $h3; for my $d (1 .. $ph3-1) { # Jameseon procedure page 6 next if ((-$p*$p) % $h3) != ($d % $h3); next if (($p-1)*$ph3) % $d; my $q = 1 + ($p-1)*$ph3 / $d; # Jameson eq 7 next unless is_prime($q); my $r = 1 + ($p*$q-1) / $h3; # Jameson eq 6 next unless is_prime($r); next unless ($q*$r) % ($p-1) == 1; printf "%2d x %5d x %5d = %s\n",$p,$q,$r,vecprod($p,$q,$r); } }
} 3,61;</lang>
- Output:
3 x 11 x 17 = 561 5 x 29 x 73 = 10585 5 x 17 x 29 = 2465 5 x 13 x 17 = 1105 ... full output is 69 lines ... 61 x 661 x 2521 = 101649241 61 x 271 x 571 = 9439201 61 x 241 x 421 = 6189121 61 x 3361 x 4021 = 824389441
Perl 6
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>
- Output:
3 × 11 × 17 == 561 5 × 29 × 73 == 10585 5 × 17 × 29 == 2465 5 × 13 × 17 == 1105 7 × 19 × 67 == 8911 7 × 31 × 73 == 15841 7 × 13 × 31 == 2821 7 × 23 × 41 == 6601 7 × 73 × 103 == 52633 7 × 13 × 19 == 1729 13 × 61 × 397 == 314821 13 × 37 × 241 == 115921 13 × 97 × 421 == 530881 13 × 37 × 97 == 46657 13 × 37 × 61 == 29341 17 × 41 × 233 == 162401 17 × 353 × 1201 == 7207201 19 × 43 × 409 == 334153 19 × 199 × 271 == 1024651 23 × 199 × 353 == 1615681 29 × 113 × 1093 == 3581761 29 × 197 × 953 == 5444489 31 × 991 × 15361 == 471905281 31 × 61 × 631 == 1193221 31 × 151 × 1171 == 5481451 31 × 61 × 271 == 512461 31 × 61 × 211 == 399001 31 × 271 × 601 == 5049001 31 × 181 × 331 == 1857241 37 × 109 × 2017 == 8134561 37 × 73 × 541 == 1461241 37 × 613 × 1621 == 36765901 37 × 73 × 181 == 488881 37 × 73 × 109 == 294409 41 × 1721 × 35281 == 2489462641 41 × 881 × 12041 == 434932961 41 × 101 × 461 == 1909001 41 × 241 × 761 == 7519441 41 × 241 × 521 == 5148001 41 × 73 × 137 == 410041 41 × 61 × 101 == 252601 43 × 631 × 13567 == 368113411 43 × 271 × 5827 == 67902031 43 × 127 × 2731 == 14913991 43 × 127 × 1093 == 5968873 43 × 211 × 757 == 6868261 43 × 631 × 1597 == 43331401 43 × 127 × 211 == 1152271 43 × 211 × 337 == 3057601 43 × 433 × 643 == 11972017 43 × 547 × 673 == 15829633 43 × 3361 × 3907 == 564651361 47 × 3359 × 6073 == 958762729 47 × 1151 × 1933 == 104569501 47 × 3727 × 5153 == 902645857 53 × 157 × 2081 == 17316001 53 × 79 × 599 == 2508013 53 × 157 × 521 == 4335241 59 × 1451 × 2089 == 178837201 61 × 421 × 12841 == 329769721 61 × 181 × 5521 == 60957361 61 × 1301 × 19841 == 1574601601 61 × 277 × 2113 == 35703361 61 × 181 × 1381 == 15247621 61 × 541 × 3001 == 99036001 61 × 661 × 2521 == 101649241 61 × 271 × 571 == 9439201 61 × 241 × 421 == 6189121 61 × 3361 × 4021 == 824389441 67 × 2311 × 51613 == 7991602081 67 × 331 × 7393 == 163954561 67 × 331 × 463 == 10267951
PicoLisp
<lang PicoLisp>(de modulo (X Y)
(% (+ Y (% X Y)) Y) )
(de prime? (N)
(let D 0 (or (= N 2) (and (> N 1) (bit? 1 N) (for (D 3 T (+ D 2)) (T (> D (sqrt N)) T) (T (=0 (% N D)) NIL) ) ) ) ) )
(for P1 61
(when (prime? P1) (for (H3 2 (> P1 H3) (inc H3)) (let G (+ H3 P1) (for (D 1 (> G D) (inc D)) (when (and (=0 (% (* G (dec P1)) D) ) (= (modulo (* (- P1) P1) H3) (% D H3)) ) (let (P2 (inc (/ (* (dec P1) G) D) ) P3 (inc (/ (* P1 P2) H3)) ) (when (and (prime? P2) (prime? P3) (= 1 (modulo (* P2 P3) (dec P1))) ) (print (list P1 P2 P3)) ) ) ) ) ) ) ) )
(prinl)
(bye)</lang>
PL/I
<lang PL/I>Carmichael: procedure options (main, reorder); /* 24 January 2014 */
declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);
put ('Carmichael numbers are:');
do Prime1 = 1 to 61;
do h3 = 2 to Prime1;
d_loop: do d = 1 to h3+Prime1-1;
if (mod((h3+Prime1)*(Prime1-1), d) = 0) & (mod(-Prime1*Prime1, h3) = mod(d, h3)) then do; Prime2 = (Prime1-1) * (h3+Prime1)/d; Prime2 = Prime2 + 1; if ^is_prime(Prime2) then iterate d_loop; Prime3 = Prime1*Prime2/h3; Prime3 = Prime3 + 1; if ^is_prime(Prime3) then iterate d_loop; if mod(Prime2*Prime3, Prime1-1) ^= 1 then iterate d_loop; put skip edit (trim(Prime1), ' x ', trim(Prime2), ' x ', trim(Prime3)) (A); end; end; end; end;
/* Uses is_prime from Rosetta Code PL/I. */
end Carmichael;</lang> Results:
Carmichael numbers are: 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 7 x 73 x 103 7 x 13 x 19 9 x 89 x 401 9 x 29 x 53 13 x 61 x 397 13 x 37 x 241 13 x 97 x 421 13 x 37 x 97 13 x 37 x 61 17 x 41 x 233 17 x 353 x 1201 19 x 43 x 409 19 x 199 x 271 21 x 761 x 941 23 x 199 x 353 27 x 131 x 443 27 x 53 x 131 29 x 113 x 1093 29 x 197 x 953 31 x 991 x 15361 31 x 61 x 631 31 x 151 x 1171 31 x 61 x 271 31 x 61 x 211 31 x 271 x 601 31 x 181 x 331 35 x 647 x 7549 35 x 443 x 3877 37 x 109 x 2017 37 x 73 x 541 37 x 613 x 1621 37 x 73 x 181 37 x 73 x 109 41 x 1721 x 35281 41 x 881 x 12041 41 x 101 x 461 41 x 241 x 761 41 x 241 x 521 41 x 73 x 137 41 x 61 x 101 43 x 631 x 13567 43 x 271 x 5827 43 x 127 x 2731 43 x 127 x 1093 43 x 211 x 757 43 x 631 x 1597 43 x 127 x 211 43 x 211 x 337 43 x 433 x 643 43 x 547 x 673 43 x 3361 x 3907 47 x 3359 x 6073 47 x 1151 x 1933 47 x 3727 x 5153 49 x 313 x 5113 49 x 97 x 433 51 x 701 x 7151 53 x 157 x 2081 53 x 79 x 599 53 x 157 x 521 55 x 3079 x 84673 55 x 163 x 4483 55 x 1567 x 28729 55 x 109 x 1999 55 x 433 x 2647 55 x 919 x 3889 55 x 139 x 547 55 x 3889 x 12583 55 x 109 x 163 55 x 433 x 487 57 x 113 x 1289 57 x 113 x 281 57 x 4649 x 10193 59 x 1451 x 2089 61 x 421 x 12841 61 x 181 x 5521 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
Python
<lang python>class Isprime():
Extensible sieve of Eratosthenes >>> isprime.check(11) True >>> isprime.multiples {2, 4, 6, 8, 9, 10} >>> isprime.primes [2, 3, 5, 7, 11] >>> isprime(13) True >>> isprime.multiples {2, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22} >>> isprime.primes [2, 3, 5, 7, 11, 13, 17, 19] >>> isprime.nmax 22 >>> multiples = {2} primes = [2] nmax = 2 def __init__(self, nmax): if nmax > self.nmax: self.check(nmax)
def check(self, n): if type(n) == float: if not n.is_integer(): return False n = int(n) multiples = self.multiples if n <= self.nmax: return n not in multiples else: # Extend the sieve primes, nmax = self.primes, self.nmax newmax = max(nmax*2, n) for p in primes: multiples.update(range(p*((nmax + p + 1) // p), newmax+1, p)) for i in range(nmax+1, newmax+1): if i not in multiples: primes.append(i) multiples.update(range(i*2, newmax+1, i)) self.nmax = newmax return n not in multiples
__call__ = check
def carmichael(p1):
ans = [] if isprime(p1): for h3 in range(2, p1): g = h3 + p1 for d in range(1, g): if (g * (p1 - 1)) % d == 0 and (-p1 * p1) % h3 == d % h3: p2 = 1 + ((p1 - 1)* g // d) if isprime(p2): p3 = 1 + (p1 * p2 // h3) if isprime(p3): if (p2 * p3) % (p1 - 1) == 1: #print('%i X %i X %i' % (p1, p2, p3)) ans += [tuple(sorted((p1, p2, p3)))] return ans
isprime = Isprime(2)
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>
- Output:
(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19), (7, 13, 31), (7, 19, 67), (7, 23, 41), (7, 31, 73), (7, 73, 103), (13, 37, 61), (13, 37, 97), (13, 37, 241), (13, 61, 397), (13, 97, 421), (17, 41, 233), (17, 353, 1201), (19, 43, 409), (19, 199, 271), (23, 199, 353), (29, 113, 1093), (29, 197, 953), (31, 61, 211), (31, 61, 271), (31, 61, 631), (31, 151, 1171), (31, 181, 331), (31, 271, 601), (31, 991, 15361), (37, 73, 109), (37, 73, 181), (37, 73, 541), (37, 109, 2017), (37, 613, 1621), (41, 61, 101), (41, 73, 137), (41, 101, 461), (41, 241, 521), (41, 241, 761), (41, 881, 12041), (41, 1721, 35281), (43, 127, 211), (43, 127, 1093), (43, 127, 2731), (43, 211, 337), (43, 211, 757), (43, 271, 5827), (43, 433, 643), (43, 547, 673), (43, 631, 1597), (43, 631, 13567), (43, 3361, 3907), (47, 1151, 1933), (47, 3359, 6073), (47, 3727, 5153), (53, 79, 599), (53, 157, 521), (53, 157, 2081), (59, 1451, 2089), (61, 181, 1381), (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)
Racket
<lang racket>
- lang racket
(require math)
(for ([p1 (in-range 3 62)] #:when (prime? p1))
(for ([h3 (in-range 2 p1)]) (define g (+ p1 h3)) (let next ([d 1]) (when (< d g) (when (and (zero? (modulo (* g (- p1 1)) d)) (= (modulo (- (sqr p1)) h3) (modulo d h3))) (define p2 (+ 1 (quotient (* g (- p1 1)) d))) (when (prime? p2) (define p3 (+ 1 (quotient (* p1 p2) h3))) (when (and (prime? p3) (= 1 (modulo (* p2 p3) (- p1 1)))) (displayln (list p1 p2 p3 '=> (* p1 p2 p3)))))) (next (+ d 1))))))
</lang> Output: <lang racket> (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 23 41 => 6601) (7 73 103 => 52633) (13 61 397 => 314821) (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 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 1301 19841 => 1574601601) (61 277 2113 => 35703361) (61 541 3001 => 99036001) (61 661 2521 => 101649241) (61 271 571 => 9439201) (61 241 421 => 6189121) (61 3361 4021 => 824389441) </lang>
REXX
vertical list
Note that REXX's version of modulus (//
) is really a remainder function.
The Carmichael numbers are shown in numerical order.
Some code optimization was done, while not necessary for the small default number (61), it was significant for larger numbers.
<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 /*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 /*is P a prime? No, then skip it.*/ @.=0 do h3=2 to pm; 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*/ $=0 /*display a list of some Carmichael #s.*/ do j=bot to top by 2 while tell; if @.j==0 then iterate; $=1 say 'Carmichael number: ' p "∙" j '∙' @.j end /*j*/ if $ then say /*show a blank line for beautification.*/ 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<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//17==0 then return 0; if x//19==0 then return 0 do k=23 by 6 until k*k>x; if x// k ==0 then return 0 if x//(k+2)==0 then return 0 end /*i*/ !.x=1; return 1</lang>
output when using the default input:
Carmichael number: 3 ∙ 11 ∙ 17 Carmichael number: 5 ∙ 13 ∙ 17 Carmichael number: 5 ∙ 17 ∙ 29 Carmichael number: 5 ∙ 29 ∙ 73 Carmichael number: 7 ∙ 13 ∙ 19 Carmichael number: 7 ∙ 19 ∙ 67 Carmichael number: 7 ∙ 23 ∙ 41 Carmichael number: 7 ∙ 31 ∙ 73 Carmichael number: 7 ∙ 73 ∙ 103 Carmichael number: 13 ∙ 37 ∙ 61 Carmichael number: 13 ∙ 61 ∙ 397 Carmichael number: 13 ∙ 97 ∙ 421 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.
output when using the input of: -1000
1038 Carmichael numbers found.
output when using the input of: -10000
8716 Carmichael numbers found.
horizontal list
This REXX version (pre-)generates a number of primes to assist the isPrime 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 when the following us used for input: 1000
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 ──────── 1038 Carmichael numbers found.
Ruby
<lang ruby># Generate Charmichael Numbers
require 'prime'
Prime.each(61) do |p|
(2...p).each do |h3| g = h3 + p (1...g).each do |d| next if (g*(p-1)) % d != 0 or (-p*p) % h3 != d % h3 q = 1 + ((p - 1) * g / d) next unless q.prime? r = 1 + (p * q / h3) next unless r.prime? and (q * r) % (p - 1) == 1 puts "#{p} x #{q} x #{r}" end end puts
end</lang>
- Output:
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 7 x 73 x 103 7 x 13 x 19 13 x 61 x 397 13 x 37 x 241 13 x 97 x 421 13 x 37 x 97 13 x 37 x 61 17 x 41 x 233 17 x 353 x 1201 19 x 43 x 409 19 x 199 x 271 23 x 199 x 353 29 x 113 x 1093 29 x 197 x 953 31 x 991 x 15361 31 x 61 x 631 31 x 151 x 1171 31 x 61 x 271 31 x 61 x 211 31 x 271 x 601 31 x 181 x 331 37 x 109 x 2017 37 x 73 x 541 37 x 613 x 1621 37 x 73 x 181 37 x 73 x 109 41 x 1721 x 35281 41 x 881 x 12041 41 x 101 x 461 41 x 241 x 761 41 x 241 x 521 41 x 73 x 137 41 x 61 x 101 43 x 631 x 13567 43 x 271 x 5827 43 x 127 x 2731 43 x 127 x 1093 43 x 211 x 757 43 x 631 x 1597 43 x 127 x 211 43 x 211 x 337 43 x 433 x 643 43 x 547 x 673 43 x 3361 x 3907 47 x 3359 x 6073 47 x 1151 x 1933 47 x 3727 x 5153 53 x 157 x 2081 53 x 79 x 599 53 x 157 x 521 59 x 1451 x 2089 61 x 421 x 12841 61 x 181 x 5521 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
Rust
<lang rust> fn is_prime(n: i64) -> bool {
if n > 1 { (2..((n / 2) + 1)).all(|x| n % x != 0) } else { false }
}
// The modulo operator actually calculates the remainder. fn modulo(n: i64, m: i64) -> i64 {
((n % m) + m) % m
}
fn carmichael(p1: i64) -> Vec<(i64, i64, i64)> {
let mut results = Vec::new(); if !is_prime(p1) { return results; }
for h3 in 2..p1 { for d in 1..(h3 + p1) { if (h3 + p1) * (p1 - 1) % d != 0 || modulo(-p1 * p1, h3) != d % h3 { continue; }
let p2 = 1 + ((p1 - 1) * (h3 + p1) / d); if !is_prime(p2) { continue; }
let p3 = 1 + (p1 * p2 / h3); if !is_prime(p3) || ((p2 * p3) % (p1 - 1) != 1) { continue; }
results.push((p1, p2, p3)); } }
results
}
fn main() {
(1..62) .filter(|&x| is_prime(x)) .map(carmichael) .filter(|x| !x.is_empty()) .flat_map(|x| x) .inspect(|x| println!("{:?}", x)) .count(); // Evaluate entire iterator
} </lang>
- Output:
(3, 11, 17) (5, 29, 73) (5, 17, 29) (5, 13, 17) . . . (61, 661, 2521) (61, 271, 571) (61, 241, 421) (61, 3361, 4021)
Seed7
The function isPrime below is borrowed from the Seed7 algorithm collection.
<lang seed7>$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
result var boolean: prime is FALSE; local var integer: upTo is 0; var integer: testNum is 3; begin if number = 2 then prime := TRUE; elsif odd(number) and number > 2 then upTo := sqrt(number); while number rem testNum <> 0 and testNum <= upTo do testNum +:= 2; end while; prime := testNum > upTo; end if; end func;
const proc: main is func
local var integer: p1 is 0; var integer: h3 is 0; var integer: g is 0; var integer: d is 0; var integer: p2 is 0; var integer: p3 is 0; begin for p1 range 2 to 61 do if isPrime(p1) then for h3 range 2 to p1 do g := h3 + p1; for d range 1 to pred(g) do if (g * pred(p1)) mod d = 0 and -p1 ** 2 mod h3 = d mod h3 then p2 := 1 + pred(p1) * g div d; if isPrime(p2) then p3 := 1 + p1 * p2 div h3; if isPrime(p3) and (p2 * p3) mod pred(p1) = 1 then writeln(p1 <& " * " <& p2 <& " * " <& p3 <& " = " <& p1*p2*p3); end if; end if; end if; end for; end for; end if; end for; end func;</lang>
- Output:
3 * 11 * 17 = 561 5 * 29 * 73 = 10585 5 * 17 * 29 = 2465 5 * 13 * 17 = 1105 7 * 19 * 67 = 8911 7 * 31 * 73 = 15841 7 * 13 * 31 = 2821 7 * 23 * 41 = 6601 7 * 73 * 103 = 52633 7 * 13 * 19 = 1729 13 * 61 * 397 = 314821 13 * 37 * 241 = 115921 13 * 97 * 421 = 530881 13 * 37 * 97 = 46657 13 * 37 * 61 = 29341 17 * 41 * 233 = 162401 17 * 353 * 1201 = 7207201 19 * 43 * 409 = 334153 19 * 199 * 271 = 1024651 23 * 199 * 353 = 1615681 29 * 113 * 1093 = 3581761 29 * 197 * 953 = 5444489 31 * 991 * 15361 = 471905281 31 * 61 * 631 = 1193221 31 * 151 * 1171 = 5481451 31 * 61 * 271 = 512461 31 * 61 * 211 = 399001 31 * 271 * 601 = 5049001 31 * 181 * 331 = 1857241 37 * 109 * 2017 = 8134561 37 * 73 * 541 = 1461241 37 * 613 * 1621 = 36765901 37 * 73 * 181 = 488881 37 * 73 * 109 = 294409 41 * 1721 * 35281 = 2489462641 41 * 881 * 12041 = 434932961 41 * 101 * 461 = 1909001 41 * 241 * 761 = 7519441 41 * 241 * 521 = 5148001 41 * 73 * 137 = 410041 41 * 61 * 101 = 252601 43 * 631 * 13567 = 368113411 43 * 271 * 5827 = 67902031 43 * 127 * 2731 = 14913991 43 * 127 * 1093 = 5968873 43 * 211 * 757 = 6868261 43 * 631 * 1597 = 43331401 43 * 127 * 211 = 1152271 43 * 211 * 337 = 3057601 43 * 433 * 643 = 11972017 43 * 547 * 673 = 15829633 43 * 3361 * 3907 = 564651361 47 * 3359 * 6073 = 958762729 47 * 1151 * 1933 = 104569501 47 * 3727 * 5153 = 902645857 53 * 157 * 2081 = 17316001 53 * 79 * 599 = 2508013 53 * 157 * 521 = 4335241 59 * 1451 * 2089 = 178837201 61 * 421 * 12841 = 329769721 61 * 181 * 5521 = 60957361 61 * 1301 * 19841 = 1574601601 61 * 277 * 2113 = 35703361 61 * 181 * 1381 = 15247621 61 * 541 * 3001 = 99036001 61 * 661 * 2521 = 101649241 61 * 271 * 571 = 9439201 61 * 241 * 421 = 6189121 61 * 3361 * 4021 = 824389441
Sidef
<lang ruby>var ntheory = frequire('ntheory');
ntheory.forprimes({ |*p|
p = Number.new(p[-1]); range(2, p-1).each { |h3| var ph3 = (p + h3); range(1, ph3-1).each { |d| ((-p * p) % h3) != (d % h3) && next; ((p-1)*ph3) % d && next; var q = 1+((p-1) * ph3 / d); ntheory.is_prime(q) || next; var r = 1+((p*q - 1)/h3); ntheory.is_prime(r) || next; (q*r) % (p-1) == 1 || next; printf("%2d x %5d x %5d = %s\n",p,q,r,ntheory.vecprod(p,q,r)); } }
}, 3, 61);</lang>
- Output:
3 x 11 x 17 = 561 5 x 29 x 73 = 10585 5 x 17 x 29 = 2465 5 x 13 x 17 = 1105 ... full output is 69 lines ... 61 x 661 x 2521 = 101649241 61 x 271 x 571 = 9439201 61 x 241 x 421 = 6189121 61 x 3361 x 4021 = 824389441
Tcl
Using the primality tester from the Miller-Rabin task... <lang tcl>proc carmichael {limit {rounds 10}} {
set carmichaels {} for {set p1 2} {$p1 <= $limit} {incr p1} {
if {![miller_rabin $p1 $rounds]} continue for {set h3 2} {$h3 < $p1} {incr h3} { set g [expr {$h3 + $p1}] for {set d 1} {$d < $h3+$p1} {incr d} { if {(($h3+$p1)*($p1-1))%$d != 0} continue if {(-($p1**2))%$h3 != $d%$h3} continue
set p2 [expr {1 + ($p1-1)*$g/$d}] if {![miller_rabin $p2 $rounds]} continue
set p3 [expr {1 + $p1*$p2/$h3}] if {![miller_rabin $p3 $rounds]} continue
if {($p2*$p3)%($p1-1) != 1} continue lappend carmichaels $p1 $p2 $p3 [expr {$p1*$p2*$p3}] } }
} return $carmichaels
}</lang> Demonstrating: <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>
- Output:
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
zkl
Using the Miller-Rabin primality test in lib GMP. <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; cs:=[[(p1,h3,d); primes; { [2..p1 - 1] }; // list comprehension
{ [1..h3 + p1 - 1] },
{ ((h3 + p1)*(p1 - 1)%d == 0 and ((-p1*p1):mod(_,h3) == d%h3)) },//guard { (p2=1 + (p1 - 1)*(h3 + p1)/d):bi.set(_).probablyPrime() },//guard { (p3=1 + (p1*p2/h3)):bi.set(_).probablyPrime() }, //guard { 1==(p2*p3)%(p1 - 1) }; //guard
{ 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> <lang>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) });</lang>
- Output:
69 Carmichael numbers found: 3 * 11 * 17 = 561 5 * 29 * 73 = 10585 5 * 17 * 29 = 2465 5 * 13 * 17 = 1105 7 * 19 * 67 = 8911 ... 61 * 181 * 1381 = 15247621 61 * 541 * 3001 = 99036001 61 * 661 * 2521 = 101649241 61 * 271 * 571 = 9439201 61 * 241 * 421 = 6189121 61 * 3361 * 4021 = 824389441
ZX Spectrum Basic
<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>