# Python code for OEIS A135027
# Michael S. Branicky, May 28 2021

# A135027  Numbers k such that the sum of the digits of k^2 is 10. Multiples of 10 are omitted.
data = [8, 19, 35, 46, 55, 71, 145, 152, 179, 251, 332, 361, 449, 451, 548, 649, 4499, 20249, 20251, 24499, 100549, 114499, 316261]

from time import time
time0 = time()


def cond_final(s): return sum(map(int, s)) == 10
def cond_inter(s): return s[-1] != '0' and sum(map(int, s)) < 10

alst = []
digits = "0123456789"
digset = set(digits)
valid = set([""])

for e in range(1, 101):
  print("Starting with", e, "digits; # to test =", len(valid), time()-time0)
  newvalid = set()
  for tstr in valid:
    for d in digset:
      dtstr = d + tstr
      dt = int(dtstr)
      remstr = str(dt**2)[-e:]
      if cond_inter(remstr):
        newvalid.add(dtstr)
        if dtstr[0] != "0":
          if cond_final(str(dt**2)):
            alst.append(dt)
            alst = sorted(set(alst))
            print("   FOUND ", dt)
            print("   alst =", alst)
            print("   data =", data)          
  valid = newvalid