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

%I #17 Aug 22 2021 13:29:49

%S 0,31,291,2421,20047,167493,1414416,12055582,103547007,895037251,

%T 7777564986,67886919436,594812780492,5228677322789,46092207649088,

%U 407310913585540,3607044214789103,32002805595571724,284404590208016926

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

%C 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.

%C 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.

%C 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.

%H Kevin Ryde, <a href="/A327561/b327561.txt">Table of n, a(n) for n = 1..1047</a>

%H Kevin Ryde, <a href="/A327561/a327561.gp.txt">Linear recurrence coefficients and generating function, in a PARI/GP script</a>

%H <a href="/index/Rec#order_983">Index entries for linear recurrences with constant coefficients</a>, order 983.

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

%Y Cf. A038770, A038772, A327560.

%K nonn,base

%O 1,2

%A _Kevin Ryde_, Sep 19 2019