Carmichael 3 strong pseudoprimes

From Rosetta Code
Task
Carmichael 3 strong pseudoprimes
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:

Prime1 × Prime2 × Prime3

where   (Prime1 < Prime2 < Prime3)   for all   Prime1   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[edit]

Uses the Miller_Rabin package from Miller-Rabin primality test#ordinary integers.

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;
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

ALGOL 68[edit]

Uses the Sieve of Eratosthenes code from the Smith Numbers task with an increased upper-bound (included here for convenience).

# sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise #
PROC sieve = ( REF[]BOOL s )VOID:
BEGIN
# start with everything flagged as prime #
FOR i TO UPB s DO s[ i ] := TRUE OD;
# sieve out the non-primes #
s[ 1 ] := FALSE;
FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO
IF s[ i ] THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := FALSE OD FI
OD
END # sieve # ;
 
# construct a sieve of primes up to the maximum number required for the task #
# For Prime1, we need to check numbers up to around 120 000 #
INT max number = 200 000;
[ 1 : max number ]BOOL is prime;
sieve( is prime );
 
# Find the Carmichael 3 Stromg Pseudoprimes for Prime1 up to 61 #
 
FOR prime1 FROM 2 TO 61 DO
IF is prime[ prime 1 ] THEN
FOR h3 TO prime1 - 1 DO
FOR d TO ( h3 + prime1 ) - 1 DO
IF ( h3 + prime1 ) * ( prime1 - 1 ) MOD d = 0
AND ( - ( prime1 * prime1 ) ) MOD h3 = d MOD h3
THEN
INT prime2 = 1 + ( ( prime1 - 1 ) * ( h3 + prime1 ) OVER d );
IF is prime[ prime2 ] THEN
INT prime3 = 1 + ( prime1 * prime2 OVER h3 );
IF is prime[ prime3 ] THEN
IF ( prime2 * prime3 ) MOD ( prime1 - 1 ) = 1 THEN
print( ( whole( prime1, 0 ), " ", whole( prime2, 0 ), " ", whole( prime3, 0 ), newline ) )
FI
FI
FI
FI
OD
OD
FI
OD
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
...
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

C[edit]

 
#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;
}
 
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[edit]

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);
}
}
}
}
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[edit]

 
;; 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)))
 
Output:
 
(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
 

Fortran[edit]

Plan[edit]

This is F77 style, and directly translates the given calculation as per formula translation. It turns out that the normal integers suffice for the demonstration, except for just one of the products of the three primes: 41x1721x35281 = 2489462641, which is bigger than 2147483647, the 32-bit limit. Fortunately, INTEGER*8 variables are also available, so the extension is easy. Otherwise, one would have to mess about with using two integers in a bignum style, one holding say the millions, and the second the number up to a million.

Integer arithmetic[edit]

Integer arithmetic can be a delicate matter, not just because of overflows. With division, sometimes the formula will never produce a remainder, as in n(n + 1)/2, and sometimes the divisor is always a factor for more complex reasons - as with (P1 - 1)*(H3 + P1)/D. But if a term produces a fractional part, is it to be discarded or not? Some languages (such as Pascal) insist on "div" instead of "/" so that one thinks about truncating division, others (such as pl/i) just generate the fractional part and proceed: perhaps the result will round? truncate? to the desired value, or perhaps other terms will cancel out the fractional parts and all will be well, or, perhaps they will combine and the result will be out by one, etc. And some formulae require the fractional parts, as in the expression for the n'th Fibonacci number where each term generates an infinite non-repeating fractional part, and, they cancel exactly, even for large values of n... In source code,

(((1 + SQRT(5))/2)**N - ((1 - SQRT(5))/2)**N)/SQRT(5)

or, in mathematical notation (possibly not rendered),

What model MOD is your MOD?[edit]

Directly translating the given formulae involves a trap. There is an expression -Prime1 squared mod h3, and translating this to MOD(-P1**2,H3) may not work. The behaviour of the MOD function for negative numbers varies between language, compiler, and cpu. For positive numbers there is no confusion. However, in some cases one wants an affine shift as in day-of-the-week calculations from a daynumber, D: given MOD(D,7), one wants the same result with MOD(D - 7,7) or any other such shift and indeed, this happens with some versions of MOD. But not all, as Prof. Knuth remarks in his description of the calculation of the date for Easter. The MOD function can also work as follows:

             D        -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7
         MOD(D,3)     -1  0 -2 -1  0 -2 -1  0  1  2  0  1  2  0  1
 MOD(3 + MOD(D,3),3)   2  0  1  2  0  1  2  0  1  2  0  1  2  0  1

Thus, MOD(-1,3) + MOD(4,3) = -1 + 1 and MOD(3,3) = 0 so that (a + b) mod n does come out as [(a mod n) + (b mod n)] mod n as is expected, but in a different way: (-1 mod 3) + (4 mod 3) = 2 + 1, thus the need for the second mod. So, MOD and mod are different. However, this MOD is consistent with integer division that truncates. If qΒ·f = n/d where q is the integer part and f the fractional part of the division, then the remainder is fd and has a sign too. Another computer/compiler/language version of MOD may not differ from mod.

Here I am supposing that (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3 is evaluated as {[(h3 + Prime1)*(Prime1 - 1) mod d] == 0} and {[-(Prime1 squared) mod h3] == d mod h3} which is to say it is [-(Prime1 squared)] mod h3 not -[(Prime1 squared) mod h3] where the first case involves the MOD(negative number) while the second is -MOD(positive number) and the only way that result could match d mod h3 is when both are zero.

Testing with the peculiar sign ignored via .AND. (MOD(P1**2,H3) .EQ. MOD(D,H3))) THEN gives limited results:

Carmichael numbers that are the product of three primes:
    P1  x P2  x P3 =         C
     3    11    17         561
     5    29    73       10585
     7    19    67        8911
    13    61   397      314821
    13    37   241      115921
    19    43   409      334153
    31   991 15361   471905281
    37   109  2017     8134561
    41  1721 35281  2489462641
    43   631 13567   368113411
    43   271  5827    67902031
    43   127  2731    14913991
    61   421 12841   329769721
    61   181  5521    60957361

Which turns out to be when the two terms have remainders of one.

Source[edit]

So, using the double MOD approach - which gives the same result for either style of MOD...
      LOGICAL FUNCTION ISPRIME(N)	!Ad-hoc, since N is not going to be big...
INTEGER N !Despite this intimidating allowance of 32 bits...
INTEGER F !A possible factor.
ISPRIME = .FALSE. !Most numbers aren't prime.
DO F = 2,SQRT(DFLOAT(N)) !Wince...
IF (MOD(N,F).EQ.0) RETURN !Not even avoiding even numbers beyond two.
END DO !Nice and brief, though.
ISPRIME = .TRUE. !No factor found.
END FUNCTION ISPRIME !So, done. Hopefully, not often.
 
PROGRAM CHASE
INTEGER P1,P2,P3 !The three primes to be tested.
INTEGER H3,D !Assistants.
INTEGER MSG !File unit number.
MSG = 6 !Standard output.
WRITE (MSG,1) !A heading would be good.
1 FORMAT ("Carmichael numbers that are the product of three primes:"
& /" P1 x P2 x P3 =",9X,"C")
DO P1 = 2,61 !Step through the specified range.
IF (ISPRIME(P1)) THEN !Selecting only the primes.
DO H3 = 2,P1 - 1 !For 1 < H3 < P1.
DO D = 1,H3 + P1 - 1 !For 0 < D < H3 + P1.
IF (MOD((H3 + P1)*(P1 - 1),D).EQ.0 !Filter.
& .AND. (MOD(H3 + MOD(-P1**2,H3),H3) .EQ. MOD(D,H3))) THEN !Beware MOD for negative numbers! MOD(-P1**2, may surprise...
P2 = 1 + (P1 - 1)*(H3 + P1)/D !Candidate for the second prime.
IF (ISPRIME(P2)) THEN !Is it prime?
P3 = 1 + P1*P2/H3 !Yes. Candidate for the third prime.
IF (ISPRIME(P3)) THEN !Is it prime?
IF (MOD(P2*P3,P1 - 1).EQ.1) THEN !Yes! Final test.
WRITE (MSG,2) P1,P2,P3, INT8(P1)*P2*P3 !Result!
2 FORMAT (3I6,I12)
END IF
END IF
END IF
END IF
END DO
END DO
END IF
END DO
END

Output[edit]

Carmichael numbers that are the product of three primes:
    P1  x P2  x P3 =         C
     3    11    17         561
     5    29    73       10585
     5    17    29        2465
     5    13    17        1105
     7    19    67        8911
     7    31    73       15841
     7    13    31        2821
     7    23    41        6601
     7    73   103       52633
     7    13    19        1729
    13    61   397      314821
    13    37   241      115921
    13    97   421      530881
    13    37    97       46657
    13    37    61       29341
    17    41   233      162401
    17   353  1201     7207201
    19    43   409      334153
    19   199   271     1024651
    23   199   353     1615681
    29   113  1093     3581761
    29   197   953     5444489
    31   991 15361   471905281
    31    61   631     1193221
    31   151  1171     5481451
    31    61   271      512461
    31    61   211      399001
    31   271   601     5049001
    31   181   331     1857241
    37   109  2017     8134561
    37    73   541     1461241
    37   613  1621    36765901
    37    73   181      488881
    37    73   109      294409
    41  1721 35281  2489462641
    41   881 12041   434932961
    41   101   461     1909001
    41   241   761     7519441
    41   241   521     5148001
    41    73   137      410041
    41    61   101      252601
    43   631 13567   368113411
    43   271  5827    67902031
    43   127  2731    14913991
    43   127  1093     5968873
    43   211   757     6868261
    43   631  1597    43331401
    43   127   211     1152271
    43   211   337     3057601
    43   433   643    11972017
    43   547   673    15829633
    43  3361  3907   564651361
    47  3359  6073   958762729
    47  1151  1933   104569501
    47  3727  5153   902645857
    53   157  2081    17316001
    53    79   599     2508013
    53   157   521     4335241
    59  1451  2089   178837201
    61   421 12841   329769721
    61   181  5521    60957361
    61  1301 19841  1574601601
    61   277  2113    35703361
    61   181  1381    15247621
    61   541  3001    99036001
    61   661  2521   101649241
    61   271   571     9439201
    61   241   421     6189121
    61  3361  4021   824389441

FreeBASIC[edit]

' 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
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

Haskell[edit]

Translation of: Ruby
Library: primes
Works with: GHC version 7.4.1
Works with: primes version 0.2.1.0
#!/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
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[edit]

The following works in both languages.

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

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[edit]

Translation of: D
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);
}
}
}
}
}
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[edit]

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

 
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
 

Main

 
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.")
 
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.

Kotlin[edit]

Translation of: D
fun Int.isPrime(): Boolean {
when {
this == 2 -> return true
this <= 1 || this % 2 == 0 -> return false
else -> {
val max = Math.sqrt(toDouble()).toInt()
for (n in 3..max step 2)
if (this % n == 0) return false
return true
}
}
}
 
fun mod(n: Int, m: Int) = ((n % m) + m) % m
 
fun main(args: Array<String>) {
for (p1 in 3..61)
if (p1.isPrime())
for (h3 in 2..p1-1) {
val g = h3 + p1
for (d in 1..g-1)
if ((g * (p1 - 1)) % d == 0 && mod(-p1 * p1, h3) == d % h3) {
val q = 1 + (p1 - 1) * g / d
if (q.isPrime()) {
val r = 1 + (p1 * q / h3)
if (r.isPrime() && (q * r) % (p1 - 1) == 1)
println("$p1 x $q x $r")
}
}
}
}
Output:

See D output.

Mathematica / Wolfram Language[edit]

Cases[Cases[
Cases[Table[{p1, h3, d}, {p1, Array[Prime, [email protected]]}, {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]]

PARI/GP[edit]

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]", ")))
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[edit]

Library: ntheory
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;
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[edit]

Works with: Rakudo version 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.)

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

PicoLisp[edit]

(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)

PL/I[edit]

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;

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[edit]

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)))
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[edit]

 
#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))))))
 

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 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)
 

REXX[edit]

slightly optimized[edit]

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.

/*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*/
#=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*/
if \isPrime(p) then iterate; nps=-p*p /*is P a prime? No, then skip it.*/
 !.=0 /*the list of Carmichael #'s (so far).*/
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
#=#+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*/
end /*h3*/
$= /*display a list of some Carmichael #s.*/
do j=bot to top by 2 while tell; if !.j\==0 then $=$ p"βˆ™"j'βˆ™'!.j
end /*j*/
 
if $\=='' then say 'Carmichael number: ' strip($)
end /*p*/
say
say '──────── ' # " 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
do k=11 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

output   when using the default input:

Carmichael number:  3βˆ™11βˆ™17
Carmichael number:  5βˆ™13βˆ™17 5βˆ™17βˆ™29 5βˆ™29βˆ™73
Carmichael number:  7βˆ™13βˆ™19 7βˆ™19βˆ™67 7βˆ™23βˆ™41 7βˆ™31βˆ™73 7βˆ™73βˆ™103
Carmichael number:  13βˆ™37βˆ™61 13βˆ™61βˆ™397 13βˆ™97βˆ™421
Carmichael number:  17βˆ™41βˆ™233 17βˆ™353βˆ™1201
Carmichael number:  19βˆ™43βˆ™409 19βˆ™199βˆ™271
Carmichael number:  23βˆ™199βˆ™353
Carmichael number:  29βˆ™113βˆ™1093 29βˆ™197βˆ™953
Carmichael number:  31βˆ™61βˆ™211 31βˆ™151βˆ™1171 31βˆ™181βˆ™331 31βˆ™271βˆ™601 31βˆ™991βˆ™15361
Carmichael number:  37βˆ™73βˆ™109 37βˆ™109βˆ™2017 37βˆ™613βˆ™1621
Carmichael number:  41βˆ™61βˆ™101 41βˆ™73βˆ™137 41βˆ™101βˆ™461 41βˆ™241βˆ™521 41βˆ™881βˆ™12041 41βˆ™1721βˆ™35281
Carmichael number:  43βˆ™127βˆ™211 43βˆ™211βˆ™337 43βˆ™271βˆ™5827 43βˆ™433βˆ™643 43βˆ™547βˆ™673 43βˆ™631βˆ™1597 43βˆ™3361βˆ™3907
Carmichael number:  47βˆ™1151βˆ™1933 47βˆ™3359βˆ™6073 47βˆ™3727βˆ™5153
Carmichael number:  53βˆ™79βˆ™599 53βˆ™157βˆ™521
Carmichael number:  59βˆ™1451βˆ™2089
Carmichael number:  61βˆ™181βˆ™1381 61βˆ™241βˆ™421 61βˆ™271βˆ™571 61βˆ™277βˆ™2113 61βˆ™421βˆ™12841 61βˆ™541βˆ™3001 61βˆ™661βˆ™2521 61βˆ™1301βˆ™19841 61βˆ™3361βˆ™4021

────────  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.

more optimized[edit]

This REXX version (pre-)generates a number of primes to assist the   isPrime   function.

/*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*/
#=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 /*the list of Carmichael #'s (so far).*/
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
#=#+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*/
end /*h3*/
$= /*display a list of some Carmichael #s.*/
do j=bot to top by 2 while tell; if !.j\==0 then $=$ p"βˆ™"j'βˆ™'!.j
end /*j*/
 
if $\=='' then say 'Carmichael number: ' strip($)
end /*p*/
say
say '──────── ' # " 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.*/

output   when the following us used for input:   1000

Carmichael number:  3βˆ™11βˆ™17
Carmichael number:  5βˆ™13βˆ™17 5βˆ™17βˆ™29 5βˆ™29βˆ™73
Carmichael number:  7βˆ™13βˆ™19 7βˆ™19βˆ™67 7βˆ™23βˆ™41 7βˆ™31βˆ™73 7βˆ™73βˆ™103
Carmichael number:  13βˆ™37βˆ™61 13βˆ™61βˆ™397 13βˆ™97βˆ™421
Carmichael number:  17βˆ™41βˆ™233 17βˆ™353βˆ™1201
Carmichael number:  19βˆ™43βˆ™409 19βˆ™199βˆ™271
Carmichael number:  23βˆ™199βˆ™353
Carmichael number:  29βˆ™113βˆ™1093 29βˆ™197βˆ™953
Carmichael number:  31βˆ™61βˆ™211 31βˆ™151βˆ™1171 31βˆ™181βˆ™331 31βˆ™271βˆ™601 31βˆ™991βˆ™15361
Carmichael number:  37βˆ™73βˆ™109 37βˆ™109βˆ™2017 37βˆ™613βˆ™1621
Carmichael number:  41βˆ™61βˆ™101 41βˆ™73βˆ™137 41βˆ™101βˆ™461 41βˆ™241βˆ™521 41βˆ™881βˆ™12041 41βˆ™1721βˆ™35281
Carmichael number:  43βˆ™127βˆ™211 43βˆ™211βˆ™337 43βˆ™271βˆ™5827 43βˆ™433βˆ™643 43βˆ™547βˆ™673 43βˆ™631βˆ™1597 43βˆ™3361βˆ™3907
Carmichael number:  47βˆ™1151βˆ™1933 47βˆ™3359βˆ™6073 47βˆ™3727βˆ™5153
Carmichael number:  53βˆ™79βˆ™599 53βˆ™157βˆ™521
Carmichael number:  59βˆ™1451βˆ™2089
Carmichael number:  61βˆ™181βˆ™1381 61βˆ™241βˆ™421 61βˆ™271βˆ™571 61βˆ™277βˆ™2113 61βˆ™421βˆ™12841 61βˆ™541βˆ™3001 61βˆ™661βˆ™2521 61βˆ™1301βˆ™19841 61βˆ™3361βˆ™4021
Carmichael number:  67βˆ™331βˆ™463 67βˆ™2311βˆ™51613
Carmichael number:  71βˆ™271βˆ™521 71βˆ™421βˆ™491 71βˆ™631βˆ™701 71βˆ™701βˆ™5531 71βˆ™911βˆ™9241
Carmichael number:  73βˆ™157βˆ™2293 73βˆ™379βˆ™523 73βˆ™601βˆ™21937 73βˆ™937βˆ™13681
Carmichael number:  79βˆ™2237βˆ™25247
Carmichael number:  83βˆ™2953βˆ™4019 83βˆ™6971βˆ™289297
Carmichael number:  89βˆ™353βˆ™617 89βˆ™617βˆ™3433 89βˆ™881βˆ™7129 89βˆ™4049βˆ™120121
Carmichael number:  97βˆ™193βˆ™1249 97βˆ™673βˆ™769 97βˆ™769βˆ™10657 97βˆ™1201βˆ™38833 97βˆ™2113βˆ™5857
Carmichael number:  101βˆ™151βˆ™251 101βˆ™1301βˆ™43801
Carmichael number:  103βˆ™647βˆ™1361 103βˆ™1123βˆ™6427 103βˆ™3571βˆ™183907 103βˆ™3877βˆ™4591 103βˆ™5407βˆ™185641
Carmichael number:  107βˆ™743βˆ™1061 107βˆ™3181βˆ™26183
Carmichael number:  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 number:  113βˆ™337βˆ™449 113βˆ™827βˆ™18691 113βˆ™6833βˆ™85793 113βˆ™8737βˆ™22961
Carmichael number:  127βˆ™631βˆ™26713 127βˆ™659βˆ™1373 127βˆ™991βˆ™3313 127βˆ™2143βˆ™30241 127βˆ™16633βˆ™422479
Carmichael number:  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 number:  137βˆ™409βˆ™14009 137βˆ™953βˆ™5441 137βˆ™3673βˆ™20129 137βˆ™5441βˆ™11833
Carmichael number:  139βˆ™691βˆ™829 139βˆ™3359βˆ™66701 139βˆ™4003βˆ™92737 139βˆ™4969βˆ™8971 139βˆ™17389βˆ™21391
Carmichael number:  149βˆ™593βˆ™29453 149βˆ™1481βˆ™3109
Carmichael number:  151βˆ™211βˆ™541 151βˆ™331βˆ™3571 151βˆ™601βˆ™751 151βˆ™701βˆ™1451 151βˆ™751βˆ™8101 151βˆ™2551βˆ™192601 151βˆ™4951βˆ™53401
Carmichael number:  157βˆ™313βˆ™1093 157βˆ™937βˆ™6397 157βˆ™1093βˆ™15601 157βˆ™2017βˆ™28789 157βˆ™4993βˆ™11701 157βˆ™26053βˆ™409033
Carmichael number:  163βˆ™379βˆ™2377 163βˆ™487βˆ™811 163βˆ™811βˆ™1297 163βˆ™1297βˆ™42283 163βˆ™1621βˆ™37747
Carmichael number:  167βˆ™4483βˆ™34031 167βˆ™29383βˆ™490697
Carmichael number:  173βˆ™1291βˆ™31907 173βˆ™10321βˆ™255077 173βˆ™36809βˆ™155317
Carmichael number:  179βˆ™1069βˆ™4451 179βˆ™3739βˆ™7121 179βˆ™9257βˆ™57139 179βˆ™10859βˆ™485941
Carmichael number:  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 number:  191βˆ™421βˆ™431 191βˆ™571βˆ™15581 191βˆ™1901βˆ™7411 191βˆ™3877βˆ™56963 191βˆ™12541βˆ™342191
Carmichael number:  193βˆ™257βˆ™1601 193βˆ™401βˆ™11057 193βˆ™577βˆ™5569 193βˆ™1249βˆ™2593 193βˆ™2689βˆ™30529 193βˆ™7681βˆ™211777 193βˆ™61057βˆ™94273
Carmichael number:  199βˆ™397βˆ™4159 199βˆ™859βˆ™2311 199βˆ™937βˆ™20719 199βˆ™991βˆ™32869 199βˆ™4159βˆ™8713 199βˆ™8713βˆ™82567
Carmichael number:  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 number:  223βˆ™1777βˆ™23311 223βˆ™2221βˆ™5107 223βˆ™5107βˆ™37963 223βˆ™14653βˆ™79699 223βˆ™25087βˆ™1864801
Carmichael number:  227βˆ™1583βˆ™6781 227βˆ™2713βˆ™5651 227βˆ™7459βˆ™423299 227βˆ™21019βˆ™91757
Carmichael number:  229βˆ™457βˆ™2053 229βˆ™571βˆ™4219 229βˆ™1597βˆ™182857 229βˆ™2243βˆ™73379 229βˆ™7069βˆ™32377
Carmichael number:  233βˆ™5569βˆ™185369
Carmichael number:  239βˆ™409βˆ™3911 239βˆ™1429βˆ™1667 239βˆ™1667βˆ™6427 239βˆ™32369βˆ™234431
Carmichael number:  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 number:  251βˆ™751βˆ™3251 251βˆ™2251βˆ™56501 251βˆ™3251βˆ™4001 251βˆ™4751βˆ™22501 251βˆ™16001βˆ™803251 251βˆ™22501βˆ™297251 251βˆ™31751βˆ™2656501
Carmichael number:  257βˆ™641βˆ™1153 257βˆ™769βˆ™49409 257βˆ™67073βˆ™3447553 257βˆ™78593βˆ™403969
Carmichael number:  263βˆ™787βˆ™2621 263βˆ™1049βˆ™3407 263βˆ™6551βˆ™12577 263βˆ™71527βˆ™1881161
Carmichael number:  269βˆ™1877βˆ™126229 269βˆ™4289βˆ™384581 269βˆ™10453βˆ™65393 269βˆ™15277βˆ™21977
Carmichael number:  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 number:  277βˆ™829βˆ™7177 277βˆ™1381βˆ™1933 277βˆ™3313βˆ™9661 277βˆ™6073βˆ™31741 277βˆ™18493βˆ™88321 277βˆ™19597βˆ™36433
Carmichael number:  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 number:  283βˆ™4231βˆ™598687 283βˆ™17203βˆ™58657
Carmichael number:  293βˆ™877βˆ™4673 293βˆ™1607βˆ™31391 293βˆ™3943βˆ™5987
Carmichael number:  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 number:  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 number:  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 number:  317βˆ™18013βˆ™41081 317βˆ™104281βˆ™2542853
Carmichael number:  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 number:  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 number:  347βˆ™3461βˆ™92383 347βˆ™4153βˆ™29411
Carmichael number:  349βˆ™929βˆ™7541 349βˆ™1741βˆ™2089 349βˆ™3191βˆ™12239 349βˆ™4177βˆ™20533 349βˆ™122149βˆ™21315001
Carmichael number:  353βˆ™617βˆ™19801 353βˆ™1153βˆ™5153 353βˆ™1321βˆ™66617 353βˆ™13217βˆ™77761 353βˆ™130241βˆ™2704417
Carmichael number:  359βˆ™43319βˆ™3887881 359βˆ™46183βˆ™592133
Carmichael number:  367βˆ™733βˆ™1831 367βˆ™1831βˆ™9883 367βˆ™5003βˆ™42701 367βˆ™9151βˆ™419803 367βˆ™24889βˆ™51607 367βˆ™28183βˆ™574621
Carmichael number:  373βˆ™1117βˆ™1861 373βˆ™1613βˆ™150413 373βˆ™5581βˆ™1040857 373βˆ™16741βˆ™81097 373βˆ™139501βˆ™26016937
Carmichael number:  379βˆ™631βˆ™9199 379βˆ™757βˆ™4159 379βˆ™2269βˆ™24571 379βˆ™2539βˆ™21871 379βˆ™6427βˆ™202987 379βˆ™9829βˆ™17011 379βˆ™10639βˆ™268813
Carmichael number:  383βˆ™33617βˆ™40111 383βˆ™38201βˆ™860647 383βˆ™74873βˆ™3186263
Carmichael number:  389βˆ™3299βˆ™6791
Carmichael number:  397βˆ™1783βˆ™4951 397βˆ™2971βˆ™51283 397βˆ™4357βˆ™8317 397βˆ™30097βˆ™56629 397βˆ™55837βˆ™852589 397βˆ™79201βˆ™10480933 397βˆ™99793βˆ™370261
Carmichael number:  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 number:  409βˆ™2857βˆ™6529 409βˆ™6121βˆ™96289 409βˆ™6529βˆ™22441 409βˆ™7039βˆ™575791 409βˆ™35089βˆ™683401 409βˆ™36721βˆ™114649
Carmichael number:  419βˆ™15467βˆ™47653 419βˆ™22573βˆ™78167 419βˆ™47653βˆ™539639
Carmichael number:  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 number:  431βˆ™1721βˆ™29671 431βˆ™1979βˆ™142159 431βˆ™8171βˆ™55901 431βˆ™13331βˆ™168991
Carmichael number:  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 number:  439βˆ™3067βˆ™673207 439βˆ™3943βˆ™45553 439βˆ™9199βˆ™2019181 439βˆ™10513βˆ™17959 439βˆ™64679βˆ™7098521 439βˆ™96799βˆ™14164921
Carmichael number:  443βˆ™1327βˆ™4421 443βˆ™2029βˆ™4967 443βˆ™74257βˆ™143651 443βˆ™102103βˆ™2380613 443βˆ™167077βˆ™236471 443βˆ™251057βˆ™889747
Carmichael number:  449βˆ™2689βˆ™3137 449βˆ™50849βˆ™4566241 449βˆ™145601βˆ™325249 449βˆ™202049βˆ™45360001
Carmichael number:  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 number:  461βˆ™691βˆ™1151 461βˆ™1013βˆ™38917 461βˆ™1381βˆ™159161 461βˆ™3541βˆ™23321 461βˆ™5981βˆ™24841 461βˆ™26681βˆ™4099981
Carmichael number:  463βˆ™2927βˆ™15401 463βˆ™6007βˆ™39733 463βˆ™214831βˆ™49733377 463βˆ™218527βˆ™10117801
Carmichael number:  467βˆ™141199βˆ™474389
Carmichael number:  479βˆ™57839βˆ™219881
Carmichael number:  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 number:  491βˆ™1471βˆ™10781 491βˆ™6959βˆ™569479 491βˆ™16661βˆ™154351 491βˆ™41651βˆ™46061 491βˆ™122501βˆ™6683111 491βˆ™386611βˆ™637001
Carmichael number:  499βˆ™997βˆ™4483 499βˆ™10459βˆ™39841
Carmichael number:  503βˆ™5021βˆ™21587
Carmichael number:  509βˆ™3557βˆ™41149 509βˆ™7621βˆ™23369 509βˆ™11939βˆ™110491 509βˆ™86869βˆ™11054081
Carmichael number:  521βˆ™1301βˆ™8581 521βˆ™21841βˆ™41081
Carmichael number:  523βˆ™1567βˆ™163909 523βˆ™6091βˆ™1592797 523βˆ™9397βˆ™140419 523βˆ™15661βˆ™481807 523βˆ™38629βˆ™69427 523βˆ™155557βˆ™1114471 523βˆ™193663βˆ™462493
Carmichael number:  541βˆ™811βˆ™3511 541βˆ™1621βˆ™7561 541βˆ™6661βˆ™257401 541βˆ™7561βˆ™54541 541βˆ™12421βˆ™197641 541βˆ™16561βˆ™814501
Carmichael number:  547βˆ™1093βˆ™2731 547βˆ™2731βˆ™6553 547βˆ™6553βˆ™35491 547βˆ™7333βˆ™235951 547βˆ™26209βˆ™186187 547βˆ™52963βˆ™827737 547βˆ™158341βˆ™2624623
Carmichael number:  557βˆ™1669βˆ™42257 557βˆ™38921βˆ™7226333
Carmichael number:  563βˆ™28663βˆ™329333
Carmichael number:  569βˆ™2273βˆ™117577 569βˆ™13633βˆ™1108169 569βˆ™17609βˆ™25561 569βˆ™21017βˆ™37489 569βˆ™22153βˆ™787817
Carmichael number:  571βˆ™661βˆ™16411 571βˆ™2281βˆ™2851 571βˆ™2851βˆ™13681 571βˆ™6841βˆ™43891 571βˆ™13681βˆ™1562371 571βˆ™65323βˆ™18649717
Carmichael number:  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 number:  587βˆ™5861βˆ™33403 587βˆ™9377βˆ™54499 587βˆ™12893βˆ™36919 587βˆ™49811βˆ™3654883
Carmichael number:  593βˆ™21017βˆ™31081 593βˆ™35521βˆ™3009137 593βˆ™176417βˆ™34871761
Carmichael number:  599βˆ™2393βˆ™84319 599βˆ™120199βˆ™17999801 599βˆ™179999βˆ™35939801 599βˆ™266111βˆ™547769 599βˆ™368369βˆ™12979591
Carmichael number:  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 number:  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 number:  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 number:  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 number:  619βˆ™1237βˆ™4327 619βˆ™2267βˆ™26987 619βˆ™5563βˆ™1721749 619βˆ™28429βˆ™703903 619βˆ™53149βˆ™56239 619βˆ™92083βˆ™452377 619βˆ™398611βˆ™9490009
Carmichael number:  631βˆ™1471βˆ™46411 631βˆ™5881βˆ™90511 631βˆ™26209βˆ™82279 631βˆ™32831βˆ™67481
Carmichael number:  641βˆ™4481βˆ™7681 641βˆ™12161βˆ™26881 641βˆ™17921βˆ™370561 641βˆ™19841βˆ™176641
Carmichael number:  643βˆ™107857βˆ™2391451
Carmichael number:  647βˆ™4523βˆ™19381 647βˆ™64601βˆ™75583 647βˆ™188633βˆ™532951 647βˆ™444449βˆ™7013623
Carmichael number:  653βˆ™13367βˆ™2909551 653βˆ™176041βˆ™732197
Carmichael number:  659βˆ™2633βˆ™5923 659βˆ™23689βˆ™624443 659βˆ™27919βˆ™34781 659βˆ™30269βˆ™92779 659βˆ™73039βˆ™6876101 659βˆ™92779βˆ™1329161
Carmichael number:  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 number:  673βˆ™1009βˆ™14449 673βˆ™2017βˆ™3361 673βˆ™3361βˆ™12097 673βˆ™13441βˆ™1292257 673βˆ™40801βˆ™155137 673βˆ™231841βˆ™9178177
Carmichael number:  677βˆ™2029βˆ™85853 677βˆ™4733βˆ™1602121 677βˆ™6761βˆ™25013 677βˆ™45293βˆ™511057
Carmichael number:  683βˆ™8867βˆ™16369 683βˆ™11161βˆ™206027 683βˆ™15749βˆ™32303 683βˆ™42967βˆ™2934647 683βˆ™94117βˆ™9183131
Carmichael number:  691βˆ™7591βˆ™2622691 691βˆ™16561βˆ™2288731 691βˆ™31051βˆ™71761 691βˆ™34501βˆ™2648911 691βˆ™69691βˆ™3009781 691βˆ™743131βˆ™1330321
Carmichael number:  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 number:  709βˆ™4957βˆ™12037 709βˆ™7789βˆ™16993 709βˆ™9677βˆ™21713 709βˆ™36109βˆ™5120257 709βˆ™210277βˆ™819157
Carmichael number:  719βˆ™97649βˆ™190271
Carmichael number:  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 number:  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 number:  739βˆ™821βˆ™4019 739βˆ™3691βˆ™454609 739βˆ™10333βˆ™2545363 739βˆ™62731βˆ™1783009 739βˆ™152029βˆ™1321759
Carmichael number:  743βˆ™6679βˆ™225569 743βˆ™6997βˆ™9011 743βˆ™596569βˆ™7266407
Carmichael number:  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 number:  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 number:  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 number:  769βˆ™6529βˆ™9601 769βˆ™41729βˆ™697601
Carmichael number:  773βˆ™22003βˆ™122363 773βˆ™44777βˆ™47093
Carmichael number:  787βˆ™3931βˆ™9433 787βˆ™5503βˆ™45589 787βˆ™106373βˆ™3348623
Carmichael number:  797βˆ™2389βˆ™476009 797βˆ™3583βˆ™16319 797βˆ™5573βˆ™11941 797βˆ™21493βˆ™428249 797βˆ™58109βˆ™7718813 797βˆ™148853βˆ™859681
Carmichael number:  809βˆ™5657βˆ™9697 809βˆ™78781βˆ™176549 809βˆ™82013βˆ™22116173 809βˆ™176549βˆ™2197357 809βˆ™453289βˆ™1171601
Carmichael number:  811βˆ™1621βˆ™438211 811βˆ™4051βˆ™19441 811βˆ™4591βˆ™744661 811βˆ™6481βˆ™17011 811βˆ™19441βˆ™3153331 811βˆ™77761βˆ™1189891 811βˆ™86131βˆ™478441
Carmichael number:  821βˆ™1231βˆ™6971 821βˆ™15581βˆ™42641 821βˆ™137597βˆ™6275953
Carmichael number:  823βˆ™2467βˆ™4111 823βˆ™4111βˆ™23017 823βˆ™4933βˆ™9043 823βˆ™27127βˆ™637873 823βˆ™341953βˆ™31269703
Carmichael number:  827βˆ™2243βˆ™2833 827βˆ™4957βˆ™5783 827βˆ™24781βˆ™476603 827βˆ™101009βˆ™2880499 827βˆ™691363βˆ™57175721
Carmichael number:  829βˆ™1657βˆ™17389 829βˆ™9109βˆ™15733 829βˆ™10949βˆ™2269181 829βˆ™24841βˆ™1872109 829βˆ™140761βˆ™5556709
Carmichael number:  839βˆ™5867βˆ™223747
Carmichael number:  853βˆ™2557βˆ™4261 853βˆ™7669βˆ™594697 853βˆ™12781βˆ™5451097 853βˆ™17041βˆ™309277 853βˆ™19597βˆ™185737
Carmichael number:  857βˆ™6421βˆ™127973 857βˆ™10273βˆ™160073 857βˆ™95873βˆ™115561 857βˆ™796937βˆ™9229393
Carmichael number:  859βˆ™2861βˆ™3719 859βˆ™8581βˆ™9439 859βˆ™9439βˆ™150151 859βˆ™27457βˆ™66067 859βˆ™321751βˆ™1039039
Carmichael number:  863βˆ™24137βˆ™38791 863βˆ™28447βˆ™153437 863βˆ™38791βˆ™62927 863βˆ™56893βˆ™68099
Carmichael number:  877βˆ™1753βˆ™56941 877βˆ™3067βˆ™30223 877βˆ™6133βˆ™8761 877βˆ™24091βˆ™7042603 877βˆ™36793βˆ™6453493 877βˆ™263677βˆ™8894029
Carmichael number:  881βˆ™2861βˆ™840181 881βˆ™22441βˆ™57641 881βˆ™130241βˆ™16391761
Carmichael number:  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 number:  887βˆ™14177βˆ™50503
Carmichael number:  907βˆ™7853βˆ™16007 907βˆ™137713βˆ™24981139
Carmichael number:  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 number:  919βˆ™8263βˆ™949213 919βˆ™15607βˆ™170749 919βˆ™60589βˆ™11136259 919βˆ™129439βˆ™569161 919βˆ™156979βˆ™321301 919βˆ™311203βˆ™2918323 919βˆ™877609βˆ™21797911
Carmichael number:  929βˆ™5569βˆ™23201 929βˆ™6961βˆ™35729 929βˆ™42689βˆ™1071841 929βˆ™139201βˆ™307169
Carmichael number:  937βˆ™1873βˆ™70201 937βˆ™6553βˆ™7489 937βˆ™7489βˆ™1002457 937βˆ™21529βˆ™3362113 937βˆ™38377βˆ™5993209 937βˆ™177841βˆ™820873
Carmichael number:  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 number:  947βˆ™29327βˆ™1983763 947βˆ™47129βˆ™299539 947βˆ™307451βˆ™10398433
Carmichael number:  953βˆ™2857βˆ™9521 953βˆ™5881βˆ™18257 953βˆ™17137βˆ™69497 953βˆ™52361βˆ™159937 953βˆ™159937βˆ™2771273
Carmichael number:  967βˆ™1289βˆ™25439 967βˆ™1933βˆ™4831 967βˆ™4831βˆ™11593 967βˆ™26083βˆ™5044453 967βˆ™62791βˆ™7589863 967βˆ™88873βˆ™1909783 967βˆ™156493βˆ™30265747
Carmichael number:  971βˆ™3881βˆ™753691 971βˆ™8731βˆ™44621 971βˆ™12611βˆ™3061321 971βˆ™110581βˆ™635351 971βˆ™142591βˆ™2387171 971βˆ™169751βˆ™648931 971βˆ™1324051βˆ™3263081
Carmichael number:  977βˆ™2441βˆ™794953 977βˆ™5857βˆ™12689 977βˆ™6833βˆ™39041 977βˆ™17569βˆ™41969 977βˆ™478241βˆ™155747153
Carmichael number:  983βˆ™3929βˆ™8839 983βˆ™8839βˆ™1241249 983βˆ™970217βˆ™190744663
Carmichael number:  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 number:  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[edit]

Works with: Ruby version 1.9
# 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
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[edit]

 
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
}
 
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[edit]

The function isPrime below is borrowed from the Seed7 algorithm collection.

$ 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;
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[edit]

Translation of: Perl
func forprimes(a, b, callback) {
for (a = (a-1 -> next_prime); a <= b; a.next_prime!) {
callback(a)
}
}
 
forprimes(3, 61, func(p) {
for h3 in (2 .. p-1) {
var ph3 = (p + h3)
for d in (1 .. ph3-1) {
((-p * p) % h3) != (d % h3) && next
((p-1) * ph3) % d && next
var q = 1+((p-1) * ph3 / d)
q.is_prime || next
var r = 1+((p*q - 1)/h3)
r.is_prime || next
(q*r) % (p-1) == 1 || next
printf("%2d x %5d x %5d = %s\n",p,q,r, p*q*r)
}
}
})
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[edit]

Using the primality tester from the Miller-Rabin task...

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
}

Demonstrating:

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"
}
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[edit]

Using the Miller-Rabin primality test in lib GMP.

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 }
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) });
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[edit]

Translation of: C
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