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

Author

Kevin Ryde, Sep 19 2019

Keywords

• nonn
• base

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.

Crossrefs

Cf. A038770, A038772, A327560.

Formula

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