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


using Primes
 
function trial_pretest(k::UInt64)
 
    if ((k %  3)==0 || (k %  5)==0 || (k %  7)==0 || (k % 11)==0 ||
        (k % 13)==0 || (k % 17)==0 || (k % 19)==0 || (k % 23)==0)
        return (k <= 23)
    end
 
    return true
end
 
function gcd_pretest(k::UInt64)
 
    if (k <= 107)
        return true
    end
 
    gcd(29*31*37*41*43*47*53*59*61*67, k) == 1 &&
    gcd(71*73*79*83*89*97*101*103*107, k) == 1
end
 
function is_chernick(n::Int64, m::UInt64)
 
    t = 9*m
 
    if (!trial_pretest(6*m + 1))
        return false
    end
 
    if (!trial_pretest(12*m + 1))
        return false
    end
 
    for i in 1:n-2
        if (!trial_pretest((t << i) + 1))
            return false
        end
    end
 
    if (!gcd_pretest(6*m + 1))
        return false
    end
 
    if (!gcd_pretest(12*m + 1))
        return false
    end
 
    for i in 1:n-2
        if (!gcd_pretest((t << i) + 1))
            return false
        end
    end
 
    if (!isprime(6*m + 1))
        return false
    end
 
    if (!isprime(12*m + 1))
        return false
    end
 
    for i in 1:n-2
        if (!isprime((t << i) + 1))
            return false
        end
    end
 
    return true
end
 
function chernick_carmichael(n::Int64, m::UInt64)
    prod = big(1)
 
    prod *= 6*m + 1
    prod *= 12*m + 1
 
    for i in 1:n-2
        prod *= ((big(9)*m)<<i) + 1
    end
 
    prod
end
 
function cc_numbers(from, to)
 
    for n in from:to
 
        multiplier = 1
 
        if (n > 4) multiplier = 1 << (n-4) end
        if (n > 5) multiplier *= 5 end
 
        m = UInt64(multiplier)
 
        while true
 
            if (is_chernick(n, m))
                println("a(", n, ") = ", chernick_carmichael(n, m))
                break
            end
 
            m += multiplier
        end
    end
end
 
cc_numbers(3, 10)