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   



P
r
i
m

e

1




{\displaystyle Prime_{1}}



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



related task
Chernick's Carmichael numbers

 
show(Limit) :-
    forall(
        carmichael(Limit, P1, P2, P3, C),
        format("~w * ~w * ~w ~t~20| = ~w~n", [P1, P2, P3, C])).
 
carmichael(Upto, P1, P2, P3, X) :-
    between(2, Upto, P1),
    prime(P1),
    Limit is P1 - 1, between(2, Limit, H3),
    MaxD is H3 + P1 - 1, between(1, MaxD, D),
    (H3 + P1)*(P1 - 1) mod D =:= 0,
    -P1*P1 mod H3 =:= D mod H3,
    P2 is 1 + (P1 - 1)*(H3 + P1) div D,
    prime(P2),
    P3 is 1 + P1*P2 div H3,
    prime(P3),
    X is P1*P2*P3.
 
wheel235(L) :-
   W = [4, 2, 4, 2, 4, 6, 2, 6 | W],
   L = [1, 2, 2 | W].
 
prime(N) :-
   N >= 2,
   wheel235(W),
   prime(N, 2, W).
 
prime(N, D, _) :- D*D > N, !.
prime(N, D, [A|As]) :-
    N mod D =\= 0,
    D2 is D + A, prime(N, D2, As).
 