login
A346267
Number of n-digit integers that are divisible by all their digits.
2
9, 14, 56, 260, 1306, 7394, 43951, 273509, 1761231, 11635311, 78551945, 539622083, 3762656337, 26579694095, 189938085415, 1371475597978, 9996841746666, 73499537666630, 544684691301292, 4065992493282511, 30555869899381064, 231043525054841279, 1756887541883726014
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)
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
Cf. A034838.
Sequence in context: A272275 A272051 A272504 * A197955 A271814 A272418
KEYWORD
nonn,base
AUTHOR
Michel Marcus, Jul 12 2021
EXTENSIONS
a(9) and beyond from Michael S. Branicky, Jul 13 2021
STATUS
approved