# Python program for OEIS A276473 # Michael S Branicky, Nov 13 2024 # Uses Iterate Deepening Depth-First Search # (in order to limit memory usage) # A276473 Number of terms of A202259 with precisely n digits. data = [6, 38, 320, 2819, 25668, 237586, 2224574, 21007948] !pip3 install gmpy2 from gmpy2 import mpz, is_prime from time import time time0 = time() alst = [6] for depth in range(2, 103): reach = list("14689") # we do not include 0 after a(1), since it can't be extended alst = [None] + [6] + [0]*(depth-1) newreach = [] c = 0 while reach: q = reach.pop() if len(q) == depth: continue for d in "0123456789": s = q+d if len(s) <= depth and (d in "024568" or not is_prime(mpz(s))): reach.append(s) alst[len(s)] += 1 reach = newreach print("DONE", depth, time()-time0) print(" ", alst[1:]) print(" ", data) print("-"*80)