A327560 The number of integers m in the range 0 < m < 10^n which are divisible by one or more of their own digits (A038770).

9, 68, 708, 7578, 79952, 832506, 8585583, 87944417, 896452992, 9104962748, 92222435013, 932113080563, 9405187219507, 94771322677210, 953907792350911, 9592689086414459, 96392955785210896, 967997194404428275, 9715595409791983073

Offset: 1

Author

Kevin Ryde, Sep 16 2019

Keywords

• nonn
• base

Comments

The integers m counted are A038770, so A038770(a(n)) = 10^n-1 is the last of n digits, and A038770(a(n)+1) = 10^n is the first of n+1 digits, for n>=1.

The digit divisibility condition is a regular language so a(n) is a linear recurrence. Working through a state machine for A038770 shows the recurrence is order 984, though its characteristic polynomial factorizes over rationals into terms of orders at most 36. The recurrence begins at a(4)..a(987) giving a(988). See the links for coefficients and generating function.

The biggest root (by magnitude) of the recurrence characteristic polynomial is 10 and its g.f. coefficient is 1 which shows a(n) -> 10^n. Or simply the number of m containing at least one digit 1 (a subset of those counted here) approaches 10^n per A016189.

Links

• Kevin Ryde, Table of n, a(n) for n = 1..999
• 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 984.

Crossrefs

Cf. A038770 (digit strings), A327561 (opposite counts).

Programs

Mathematica

Accumulate@ Array[Count[Range[10^(# - 1), 10^# - 1], ?(MemberQ[Divisible[#, Cases[IntegerDigits[#], Except[0]]], True] &)] &, 7] (* _Michael De Vlieger, Sep 30 2019, after Harvey P. Dale at A038770 *)

Formula

a(n) = 10^n-1 - A327561(n).