# Python program for OEIS A361340
# Michael S. Branicky, Apr 04 2023

# A361340 a(n) = smallest number with the property that the split-and-multiply technique (see A361338) in base n can produce all n single-digit nubers.		0
data = [15, 23, 119, 167, 12049, 424, 735, 907, 17117, 1250, 307747, 2703, 49225, 9422, 57823, 5437, 2076131, 7747, 639987]

import sys
sys.set_int_max_str_digits(0)

from time import time
time0 = time()

# GLOBAL for base is faster, allows smaller cache
base = 10

from itertools import count
from sympy.ntheory import digits
from functools import lru_cache

def fd(d, b): # from_digits
    return sum(di*b**i for i, di in enumerate(d[::-1]))

@lru_cache(maxsize=None)
def f(n):
    global base
    b = base
    if n < b: return 1<<n
    s = digits(n, b)[1:]
    r = 0
    for i in range(1, len(s)):
        if s[i]!=0 or i==len(s)-1:
           r |= f(fd(s[:i], b)*fd(s[i:], b))
    return r

def a(n, printat=False):
    global base
    base = n
    f.cache_clear() # must clear cache when changing base
    # could do just the following line, but expanded for progress tracking
    #return next(k for k in count(1) if len(f(k))==n)
    for k in count(1):
        if bin(f(k)).count("1") == n:
            return k
        if printat and k%printat == 0:
            print("...", n, k, time()-time0)

alst = []
for n in range(2, 10001):
    an = a(n, printat=1000000)
    alst.append(an)
    print(n, an, len(str(alst))-2, time()-time0)
    print("   ", alst)
    print("   ", data)
    with open("b361340.txt", "a") as bfile:
        bfile.write(f"{n} {an}\n")