# Python program for OEIS A359049
# Michael S. Branicky, Dec 15 2022 

from time import time

from sympy import isprime
from itertools import count, islice
from sympy.utilities.iterables import partitions, multiset_permutations

time0 = time()
OVERLAPS = True # global switch

def count_overlaps(subs, s):
    c = i = 0
    while i != -1:
        i = s.find(subs, i)
        if i != -1: c += 1; i += 1
    return c

def count_subs(subs, s):
    global OVERLAPS
    if not OVERLAPS:
        return s.count(subs)
    return count_overlaps(subs, s)

def okstr(lst):
    M = len(lst)
    slst = "".join(str(e) for e in lst)
    return all(count_subs(str(i), slst) == lst[i] for i in range(M))

def partialokstr(lst):
    M = len(lst)
    slst = "".join(str(e) for e in lst)
    partialok, s = True, ""
    for i in range(M):
        missing = lst[i] - count_subs(str(i), slst)
        if missing < 0: return False, ""
        else: 
            if i < 10:
                s += missing*str(i)
    return True, s

def agen():
    for d in range(1, 101):
        okset = set()
        for p in partitions(d, m=10):
            #sp = "".join(str(k)*v for k, v in p.items())
            sp = []
            for k, v in p.items():
                sp.extend([k]*v)
            missing_zeros = min(d, 10) - len(sp)
            if missing_zeros < 0 or missing_zeros > 9: continue
            s = sp + [0]*missing_zeros
            for m in multiset_permutations(s):
                if m[0] != 0:
                    passes, needs = partialokstr(m)
                    if passes:
                        if d <= 10:
                            if okstr(m):
                                okset.add(int("".join(map(str, m))))
                        else:
                            if needs != "":
                                if sum(map(int, needs)) <= sum(int(m[i]) for i in range(1, d//10+1)):
                                    for m2 in multiset_permutations(needs):
                                        m2int = [int(e) for e in m2]
                                        if okstr(m+m2int):
                                            print("FOUND", m, m2int, m+m2int)
                                            okset.add(int("".join(map(str, m+m2int))))
        yield from sorted(okset)
        print("...", d, time()-time0)

alst = []
g = agen()
for n in range(1, 10001):
    an = next(g)
    alst.append(an)
    print(n, an, len(str(alst))-2, time()-time0)
    print("   ", alst)
    with open('A359049.txt', 'a') as bfile:
        bfile.write(f"{n} {an}\n")