In 1939, Jack Chernick proved that, for n ≥ 3 and m ≥ 1:

   U(n, m) = (6m + 1) * (12m + 1) * Product_{i=1..n-2} (2^i * 9m + 1)

is a Carmichael number if all the factors are primes and, for n > 4, m is a multiple of 2^(n-4).



Example
   U(3, m) = (6m + 1) * (12m + 1) * (18m + 1)
   U(4, m) = U(3, m) * (2^2 * 9m + 1)
   U(5, m) = U(4, m) * (2^3 * 9m + 1)
   ...
   U(n, m) = U(n-1, m) * (2^(n-2) * 9m + 1)

 The smallest Chernick's Carmichael number with 3 prime factors, is: U(3, 1) = 1729.
 The smallest Chernick's Carmichael number with 4 prime factors, is: U(4, 1) = 63973.
 The smallest Chernick's Carmichael number with 5 prime factors, is: U(5, 380) = 26641259752490421121.


For n = 5, the smallest number m that satisfy Chernick's conditions, is m = 380, therefore U(5, 380) is the smallest Chernick's Carmichael number with 5 prime factors.

U(5, 380) is a Chernick's Carmichael number because m = 380 is a multiple of 2^(n-4), where n = 5, and the factors { (6*380 + 1), (12*380 + 1), (18*380 + 1), (36*380 + 1), (72*380 + 1) } are all prime numbers.



Task
For n ≥ 3, let a(n) be the smallest Chernick's Carmichael number with n prime factors.

 Compute a(n) for n = 3..9.
 Optional: find a(10).

Note: it's perfectly acceptable to show the terms in factorized form:

 a(3) = 7 * 13 * 19
 a(4) = 7 * 13 * 19 * 37
 a(5) = 2281 * 4561 * 6841 * 13681 * 27361
 ...



See also
 Jack Chernick, On Fermat's simple theorem (PDF)
 OEIS A318646: The least Chernick's "universal form" Carmichael number with n prime factors


 Related tasks
 Carmichael 3 strong pseudoprimes


#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
 
typedef unsigned long long int u64;
 
#define TRUE 1
#define FALSE 0
 
int primality_pretest(u64 k) {
    if (!(k %  3) || !(k %  5) || !(k %  7) || !(k % 11) || !(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)) return (k <= 23);
    return TRUE;
}
 
int probprime(u64 k, mpz_t n) {
    mpz_set_ui(n, k);
    return mpz_probab_prime_p(n, 0);
}
 
int is_chernick(int n, u64 m, mpz_t z) {
    u64 t = 9 * m;
    if (primality_pretest(6 * m + 1) == FALSE) return FALSE;
    if (primality_pretest(12 * m + 1) == FALSE) return FALSE;
    for (int i = 1; i <= n - 2; i++) if (primality_pretest((t << i) + 1) == FALSE) return FALSE;
    if (probprime(6 * m + 1, z) == FALSE) return FALSE;
    if (probprime(12 * m + 1, z) == FALSE) return FALSE;
    for (int i = 1; i <= n - 2; i++) if (probprime((t << i) + 1, z) == FALSE) return FALSE;
    return TRUE;
}
 
int main(int argc, char const *argv[]) {
    mpz_t z;
    mpz_inits(z, NULL);
 
    for (int n = 3; n <= 10; n ++) {
        u64 multiplier = (n > 4) ? (1 << (n - 4)) : 1;
 
        if (n > 5) multiplier *= 5;
 
        for (u64 k = 1; ; k++) {
            u64 m = k * multiplier;
 
            if (is_chernick(n, m, z) == TRUE) {
                printf("a(%d) has m = %llu\n", n, m);
                break;
            }
        }
    }
 
    return 0;
}