A346267 Number of n-digit integers that are divisible by all their digits.

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

Author

Michel Marcus, Jul 12 2021

Keywords

• nonn
• base

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)

Examples

			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.
		

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).
• Kevin Ryde, Linear recurrence coefficients and generating function, in a PARI/GP script
• Kevin Ryde, Perl program making a state machine with Foma to verify the linear recurrence
• Index entries for linear recurrences with constant coefficients, order 928.

Crossrefs

Cf. A034838.

Programs

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

Extensions

a(9) and beyond from Michael S. Branicky, Jul 13 2021