OFFSET
1,1
COMMENTS
From Michael S. Branicky, Jul 13 2021: (Start)
For a(12), the count for 12-digit numbers ending in 1..9 is 89385, 126484057, 89966, 152213988, 1354818, 127833463, 72297, 131400895, 83214, resp.
Terms can be computed using reachability analysis (see program in links) on the following finite automaton with 315906 reachable states: Di = {0, ..., i-1}, D = {1, ..., 9}; P(A) denotes the power set of A; Z the empty set; U, union; Q = D2 X ... X D9 X P({2, ..., 9}), Sigma = D, s = (0, ..., 0) X Z; delta((q2, ..., q9; A), c) = (10*q2+c mod 2, ..., 10*q9+c mod 9; A'), where A' = A if c = 1 and A U c otherwise; F = {q X A | qi = 0 for i in A}.
Alternatively, the following smaller finite automaton may similarly be analyzed (see alternate program in links) to compute sequence terms: Q = {(r, m) = (remainder-so-far modulo 2520, lcm(seen digits))}; Sigma = {0, ..., 9}; s = (0, 1); F = {(r, m) | r mod m == 0}; delta((r, m), c) = (10*q+c mod 2520, lcm(r, c)) for c <> 0, delta(q, 0) dies for all q. (End)
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..1110 (terms <= 1000 digits)
Michael S. Branicky, Python program
Michael S. Branicky, Python program based on finite automaton
Michael S. Branicky, Python program based on alternate finite automaton
Michael S. Branicky, Terms 1..5000 for discovering linear recurrence
Ana Rechtman, Juillet 2021, 2e défi, Images des Mathématiques, CNRS, 2021 (in French).
EXAMPLE
In A034838, we have (1, 2, 3, 4, 5, 6, 7, 8, 9) so a(1) = 9.
And we have (11, 12, 15, 22, 24, 33, 36, 44, 48, 55, 66, 77, 88, 99) so a(2) = 14.
PROG
(PARI) is(n)=my(d=Set(digits(n))); d[1]&&!forstep(i=#d, 1, -1, n%d[i]&&return); \\ A034838
a(n) = sum(k=10^(n-1), 10^n-1, is(k));
(Python) # see links for a faster version and FA-based programs
def ok(n): return all(d != '0' and n%int(d) == 0 for d in set(str(n)))
def a(n): return sum(ok(k) for k in range(10**(n-1), 10**n))
print([a(n) for n in range(1, 7)]) # Michael S. Branicky, Jul 12 2021
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Michel Marcus, Jul 12 2021
EXTENSIONS
a(9) and beyond from Michael S. Branicky, Jul 13 2021
STATUS
approved