# Python program for OEIS A358711 # Michael S. Branicky, Dec 02 2022 # A358711 Autobiographical numbers: let the k-th digit count the k-th nonnegative integer (A001477(k)) (possibly overlapping) occurrences in the term. 0 data = [1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 53110100002, 62200010001, 541011000021, 6401101000310, 74011001003100, 840110001031000, 9321000001201000, 94201000012110000] 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(lst) return all(count_subs(str(i), slst) == int(lst[i]) for i in range(M)) def partialokstr(lst): M = len(lst) slst = "".join(lst) partialok, s = True, "" for i in range(M): missing = int(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, k=9, m=10): sp = "".join(str(k)*v for k, v in p.items()) 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(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): if okstr(m+m2): print("FOUND", "".join(m), "".join(m2), "".join(m+m2)) okset.add(int("".join(m+m2))) 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) print(" ", data) with open('b358711.txt', 'a') as bfile: bfile.write(f"{n} {an}\n")