# Python program for OEIS A377917
# Michael S. Branicky, Nov 30 2024

# # A377917 Number of n-digit terms in A377912.
data = [10, 66, 489, 3631, 26951]

"""
Performs reachability counts per digit on the following finite automaton,
which accepts A034838:
- Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 2};
- Sigma = {0, ..., 9};
- s = 1;
- F = Q - {5};
- delta(q, c) is coded below
"""

from time import time
time0 = time()

# 1: start state
# 3: last digit seen was odd
# 5: dead state (violation of constraint)
# 7: zero was seen at the start
# 0,2,4,6,8: last digit seen was even (except for 0 at start)
def delta(q, c):
    if q == 1:
        if c in {1, 3, 5, 7, 9}:
            return 3
        elif c == 0:
            return 7
        else:
            return c
    if q == 3:
        if c in {1, 3, 5, 7, 9}:
            return 3
        else:
            return c
    if q == 5:
        return 5
    if q == 7:
        return 5
    if c <= q:
        return 5
    else:
        if c in {1, 3, 5, 7, 9}:
            return 3
        else:
            return c

alst = []
s = 1
counts = {s: 1}
for n in range(1, 10001):
    A377917n = 0
    newcounts = dict()
    for c in range(10):
        for q in counts:
            newq = delta(q, c)
            if newq not in newcounts:
                newcounts[newq] = counts[q]
            else:
                newcounts[newq] += counts[q]
            if newq != 5:
                A377917n += counts[q]
    counts = newcounts
    alst.append(A377917n)
    print(n, A377917n, len(str(alst))-2, time()-time0)
    if len(str(alst)) < 280: #len(alst) <= len(data):
        print("   ", alst)
        print("   ", data)
    if len(str(A377917n)) > 1000:
        print(f"a({n}) has {len(str(A377917n))} digits. - ~~~~")
        break
    with open('b377917.txt', 'a') as bfile:
        bfile.write(f"{n} {A377917n}\n")