##========================================================
##
## palindromic.py
##
## Search for palindromic primes in base ten
##
## n is the command line argument, the number of digits
##
## Paul Soper
##
## August 6, 2018
##
##========================================================


import math
import sys
from random import randint

dg = int(sys.argv[1])

p1 = 10**(dg-1)

g = open("pr-five-palindromic-{0:03d}.dat".format(dg),"w")

pr_base = [x for x in range(2,10000) if all (x % y != 0 for y in range(2,int(math.sqrt(x)+1)))]

u = math.log(p1*10)
uu = 2.0 * u * u

bases = range(2, int(uu)+1)

def miller_rabin(n):

    if n < 2:
        return False

    # 2 is prime, and MR does not work for even numbers
    if n == 2:
        return True
    # 3 is prime - return True for 3
    if n == 3:
        return True
   
    # return False if n is even
    if not (n & 1):
        return False

    def check(a, s, d, n):
        x = pow(a, d, n)
        if x == 1:
            return True
        for i in range(s - 1):
            if x == n - 1:
                return True
            x = pow(x, 2, n)
        return x == n - 1

    s = 0
    d = n - 1
    
    while d % 2 == 0:
        d >>= 1
        s += 1
    
    for a in bases:
        if a < (n-1):
            if not check(a, s, d, n):
                return False
    return True

pa = []

while len(pa) < 5:
    n = 0
    for k in range (0,dg//2):
        r = randint(0,9)
        if k == (dg-1) and r == 0:
            r = 1
        n = n + (10**k) * r
        n = n + (10**(dg-1-k)) * r
    r = randint(0,9)
    n = n + (10**(dg//2))*r
    
    maybe_prime = True
    for t in pr_base:
        if n % t == 0:
            maybe_prime = False
            break

    if maybe_prime:
        if miller_rabin(n):
            pa.append(n)
            print ("{}".format(n))
            g.write("{}\n".format(n))
                
g.close()