

A255373


Number of strings of n decimal digits that contain at least one string of exactly 3 consecutive "0" digits.


4



0, 0, 0, 1, 18, 261, 3420, 42291, 503757, 5845383, 66525399, 745904151, 8264888316, 90700808526, 987461965116, 10678505242392, 114817381566435, 1228431892382460, 13086248073415290, 138875261344657416, 1468815363559657773, 15488131104999233505
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (20,100,0,9,99,90).


FORMULA

a(0) = a(1) = a(2) = 0, a(3) = 1, a(n) = 9*(10^(n4)  a(n4) + sum_{i=3..n1} a(i)) for n>=4.
G.f.: x^3*(x1)^2/((10*x1)*(9*x^59*x^4+10*x1)).  Alois P. Heinz, Feb 26 2015


EXAMPLE

a(3) = 1 because there is only 1 threedigit string that contains the substring "000", i.e., "000" itself.
a(4) = 18 because there are 18 fourdigit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" to represent a nonzero digit, the 18 strings comprise 9 of the form "000+" and 9 of the form "+000". ("0000" is excluded.)
a(5) = 261 because there are 261 fivedigit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" as above and "." to denote any digit (0 or otherwise), the 261 strings comprise 9*10=90 of the form "000+.", 9*9=81 of the form "+000+", and 10*9=90 of the form ".+000".
a(6) = 3420 because there are 3420 sixdigit strings that contain a "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 3420 strings comprise 9*10*10=900 of the form "000+..", 9*9*10=810 of the form "+000+.", 10*9*9=810 of the form ".+000+", and 10*10*9=900 of the form "..+000".
a(7) = 42291 because there are 42291 sevendigit strings that contain at least one "000" substring that is not part of a string of four or more consecutive "0" digits; using "+" and "." as above, the 42291 strings comprise 9*10*10*10=9000 of the form "000+...", 9*9*10*10=8100 of the form "+000+..", 10*9*9*10=8100 of the form ".+000+.", 10*10*9*9=8100 of the form "..+000+", and 999*9=8991 that are of the form "...+000" but not of the form "000+000" (since 9 strings of that latter form were already counted among the 9000 of the form "000+...").


CROSSREFS

Cf. A255371, A255372 (for the k=1 and k=2 cases of "exactly k consecutive '0' digits"), A255374A255380 (for the cases k=4 through k=10).
Sequence in context: A159537 A136660 A255372 * A255374 A255375 A255376
Adjacent sequences: A255370 A255371 A255372 * A255374 A255375 A255376


KEYWORD

nonn,base,easy


AUTHOR

Jon E. Schoenfield, Feb 22 2015


STATUS

approved



