cp's OEIS Frontend

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

%I A346267 #57 Oct 19 2024 15:57:32
%S A346267 9,14,56,260,1306,7394,43951,273509,1761231,11635311,78551945,
%T A346267 539622083,3762656337,26579694095,189938085415,1371475597978,
%U A346267 9996841746666,73499537666630,544684691301292,4065992493282511,30555869899381064,231043525054841279,1756887541883726014
%N A346267 Number of n-digit integers that are divisible by all their digits.
%C A346267 From _Michael S. Branicky_, Jul 13 2021: (Start)
%C A346267 For a(12), the count for 12-digit numbers ending in 1..9 is 89385, 126484057, 89966, 152213988, 1354818, 127833463, 72297, 131400895, 83214, resp.
%C A346267 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}.
%C A346267 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)
%H A346267 Michael S. Branicky, <a href="/A346267/b346267.txt">Table of n, a(n) for n = 1..1110</a> (terms <= 1000 digits)
%H A346267 Michael S. Branicky, <a href="/A346267/a346267.txt">Python program</a>
%H A346267 Michael S. Branicky, <a href="/A346267/a346267_1.txt">Python program based on finite automaton</a>
%H A346267 Michael S. Branicky, <a href="/A346267/a346267_2.txt">Python program based on alternate finite automaton</a>
%H A346267 Michael S. Branicky, <a href="https://drive.google.com/file/d/1ivA9VMgBupghrnAMRHJQp3gwalGUAnhe/view?usp=sharing">Terms 1..5000 for discovering linear recurrence</a>
%H A346267 Ana Rechtman, <a href="http://images-archive.math.cnrs.fr/Juillet-2021-2e-defi.html">Juillet 2021, 2e défi</a>, Images des Mathématiques, CNRS, 2021 (in French).
%H A346267 Kevin Ryde, <a href="/A346267/a346267.gp.txt">Linear recurrence coefficients and generating function, in a PARI/GP script</a>
%H A346267 Kevin Ryde, <a href="/A346267/a346267.pl.txt">Perl program making a state machine with Foma to verify the linear recurrence</a>
%H A346267 <a href="/index/Rec#order_928">Index entries for linear recurrences with constant coefficients</a>, order 928.
%e A346267 In A034838, we have (1, 2, 3, 4, 5, 6, 7, 8, 9) so a(1) = 9.
%e A346267 And we have (11, 12, 15, 22, 24, 33, 36, 44, 48, 55, 66, 77, 88, 99) so a(2) = 14.
%o A346267 (PARI) is(n)=my(d=Set(digits(n))); d[1]&&!forstep(i=#d, 1, -1, n%d[i]&&return); \\ A034838
%o A346267 a(n) = sum(k=10^(n-1), 10^n-1, is(k));
%o A346267 (Python) # see links for a faster version and FA-based programs
%o A346267 def ok(n): return all(d != '0' and n%int(d) == 0 for d in set(str(n)))
%o A346267 def a(n): return sum(ok(k) for k in range(10**(n-1), 10**n))
%o A346267 print([a(n) for n in range(1, 7)]) # _Michael S. Branicky_, Jul 12 2021
%Y A346267 Cf. A034838.
%K A346267 nonn,base
%O A346267 1,1
%A A346267 _Michel Marcus_, Jul 12 2021
%E A346267 a(9) and beyond from _Michael S. Branicky_, Jul 13 2021