I made a function that spat back all the possible next digits when you feed it two digits. I used a dictionary to keep track of the number of integers with each last two digit string. It’s really only those last two digits that you care about, after that, it’s just keeping track of how many numbers there are with those last two digits.
Script runs in under 1 second!
from itertools import *
def next_digit(a, b):
largest = 9 - a - b
return range(largest+1)
trys = dict()
for start in product(range(1,10), range(10)):
if sum(list(start)) > 9:
continue
else:
trys[start] = 1
for i in range(18):
new_trys = dict()
for t in trys.iterkeys():
for n in next_digit(t[0], t[1]):
try:
new_trys[(t[1], n)] += trys[(t[0], t[1])]
except:
new_trys[(t[1], n)] = trys[(t[0], t[1])]
trys = new_trys
total = 0
for s in trys.itervalues():
total += s
print total