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,1

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.

Formula

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

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 *)

Crossrefs

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

Sequence in context: A048742 A121633 A091708 * A024119 A348590 A120306

Adjacent sequences: A327557 A327558 A327559 * A327561 A327562 A327563

Keyword

nonn,base

Author

Kevin Ryde, Sep 16 2019

Status

approved