# Python program for OEIS A076623
# Michael S. Branicky, Apr 27 2022
# Note: uses Python's int command for speed/memory but only valid for n < 37

# A076623		Total number of left truncatable primes (without zeros) in base n.		14
data = [0, 3, 16, 15, 454, 22, 446, 108, 4260, 75, 170053, 100, 34393, 9357, 27982, 362, 14979714, 685, 3062899, 59131, 1599447, 1372, 1052029701, 10484, 7028048, 98336, 69058060, 3926]

# (Python)
from sympy import isprime, primerange
digs = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def a(n):
    prime_strs, an = [digs[p] for p in primerange(1, n)], 0
    digits = 1
    while len(prime_strs) > 0:
        an += len(prime_strs)
        print("...", n, digits, an, time()-time0)
        candidates = set(digs[d]+p for p in prime_strs for d in range(1, n))
        prime_strs = [c for c in candidates if isprime(int(c, n))]
        digits += 1
    return an

from time import time
time0 = time()

alst = []
for n in range(2, 10001):
    an = a(n)
    alst.append(an)
    print(n, an, len(str(alst))-2, time()-time0)
    print("   ", alst)
    print("   ", data)