# 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")