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

 
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
}
 