"""

Python implementation of
http://rosettacode.org/wiki/Chernick%27s_Carmichael_numbers

"""

# use sympy for prime test

from sympy import isprime

# based on C version

def primality_pretest(k):
    if not (k % 3) or not (k % 5) or not (k % 7) or not (k % 11) or not(k % 13) or not (k % 17) or not (k % 19) or not (k % 23):
        return (k <= 23)

    return True

def is_chernick(n, m):

    t = 9 * m

    if not primality_pretest(6 * m + 1):
        return False

    if not primality_pretest(12 * m + 1):
        return False

    for i in range(1,n-1):
        if not primality_pretest((t << i) + 1):
            return False

    if not isprime(6 * m + 1):
        return False

    if not isprime(12 * m + 1):
        return False

    for i in range(1,n - 1):
        if not isprime((t << i) + 1):
            return False

    return True

for n in range(3,10):

    if n > 4:
        multiplier = 1 << (n - 4)
    else:
        multiplier = 1

    if n > 5:
        multiplier *= 5


    k = 1

    while True:
        m = k * multiplier

        if is_chernick(n, m):
            print("a("+str(n)+") has m = "+str(m))
            break

        k += 1