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


import strutils, sequtils
import bignum
 
const
  Max = 10
  Factors: array[3..Max, int] = [1, 1, 2, 4, 8, 16, 32, 64]   # 1 for n=3 then 2^(n-4).
  FirstPrimes = [3, 5, 7, 11, 13, 17, 19, 23]
 
#---------------------------------------------------------------------------------------------------
 
iterator factors(n, m: Natural): Natural =
  ## Yield the factors of U(n, m).
 
  yield 6 * m + 1
  yield 12 * m + 1
  var k = 2
  for _ in 1..(n - 2):
    yield 9 * k * m + 1
    inc k, k
 
#---------------------------------------------------------------------------------------------------
 
proc mayBePrime(n: int): bool =
  ## First primality test.
 
  if n < 23: return true
 
  for p in FirstPrimes:
    if n mod p == 0:
      return false
 
  result = true
 
#---------------------------------------------------------------------------------------------------
 
proc isChernick(n, m: Natural): bool =
  ## Check if U(N, m) if a Chernick-Carmichael number.
 
  # Use the first and quick test.
  for factor in factors(n, m):
    if not factor.mayBePrime():
      return false
 
  # Use the slow probability test (need to use a big int).
  for factor in factors(n, m):
    if probablyPrime(newInt(factor), 25) == 0:
      return false
 
  result = true
 
#---------------------------------------------------------------------------------------------------
 
proc a(n: Natural): tuple[m: Natural, factors: seq[Natural]] =
  ## For a given "n", find the smallest Charnick-Carmichael number.
 
  var m: Natural = 0
  var incr = (if n >= 5: 5 else: 1) * Factors[n]  # For n >= 5, a(n) is a multiple of 5.
 
  while true:
    inc m, incr
    if isChernick(n, m):
      return (m, toSeq(factors(n, m)))
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
import strformat
 
for n in 3..Max:
  let (m, factors) = a(n)
 
  stdout.write fmt"a({n}) = U({n}, {m}) = "
  var s = ""
  for factor in factors:
    s.addSep(" × ")
    s.add($factor)
  stdout.write s, '\n'