A327561 The number of integers m in the range 0 < m < 10^n which are not divisible by any of their own digits (A038772).

0, 31, 291, 2421, 20047, 167493, 1414416, 12055582, 103547007, 895037251, 7777564986, 67886919436, 594812780492, 5228677322789, 46092207649088, 407310913585540, 3607044214789103, 32002805595571724, 284404590208016926

Offset

1,2

Comments

The integers m counted are A038772 so that A038772(a(n)) is the last there of n digits and A038772(a(n)+1) is the first there of n+1 digits, for n>=2.

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

The biggest root (by magnitude) of the characteristic polynomial is 9 and its g.f. coefficient is 4/21 which shows a(n) -> (4/21)*9^n.

Links

Kevin Ryde, Table of n, a(n) for n = 1..1047

Kevin Ryde, Linear recurrence coefficients and generating function, in a PARI/GP script

Index entries for linear recurrences with constant coefficients, order 983.

Formula

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

Crossrefs

Cf. A038770, A038772, A327560.

Sequence in context: A156094 A221430 A115151 * A279980 A369173 A001298

Adjacent sequences: A327558 A327559 A327560 * A327562 A327563 A327564

Keyword

nonn,base

Author

Kevin Ryde, Sep 19 2019

Status

approved