

A066178


Number of binary bit strings of length n with no block of 8 or more 0's. Nonzero heptanacci numbers, A122189.


26



1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776, 987568, 1967200, 3918592, 7805695, 15548665, 30972384, 61695880, 122895984, 244804400, 487641600
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Analogous bit string description and o.g.f. (1x)/(12x+x^{k+1}) works for nonzero knacci numbers.
Compositions of n into (nonzero) parts <= 7.  Joerg Arndt, Aug 06 2012


LINKS

T. D. Noe, Table of n, a(n) for n = 0..200
Martin Burtscher, Igor Szczyrba, RafaĆ Szczyrba, Analytic Representations of the nanacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Zhao Hui Du, Link giving derivation and proof of the formula
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci nstep and Lucas nstep Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
Eric Weisstein's World of Mathematics, Fibonacci nStep Number
Eric Weisstein's World of Mathematics, Heptanacci Number
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1, 1, 1, 1, 1).


FORMULA

O.g.f.: 1/(1xx^2x^3x^4x^5x^6x^7).
a(n) = Sum_{i=n7..n1} a(i).
a(n) = round({r1}/{(t+1)r2t} * r^{n1}), where r is the heptanacci constant, the real root of the equation x^{t+1)2x^t+1=0 which is greater than 1. The formula could also be used for a kstep Fibonacci sequence if r is replaced by the kbonacci constant, as in A000045, A000073, A000078, A001591, A001592.  Zhao Hui Du, Aug 24 2008
For a(0)=a(1)=1, a(2)=2, a(3)=4, a(4)=8, a(5)=16, a(6)=32, a(7)=64, a(n) = 2*a(n1)  a(n8).  Vincenzo Librandi, Dec 20 2010


MATHEMATICA

a[0] = a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 8; a[5] = 16; a[6] = 32; a[7] = 64; a[n_] := 2*a[n  1]  a[n  8]; Array[a, 31, 0]
CoefficientList[ Series[(1  x)/(1  2 x + x^8), {x, 0, 30}], x]
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1}, {1, 1, 2, 4, 8, 16, 32}, 40] (* Harvey P. Dale, Nov 16 2014 *)


CROSSREFS

Cf. A000045 (k=2, Fibonacci numbers), A000073 (k=3, tribonacci) A000078 (k=4, tetranacci) A001591 (k=5, pentanacci) A001592 (k=6, hexanacci), A122189 (k=7, heptanacci).
Row 7 of arrays A048887 and A092921 (kgeneralized Fibonacci numbers).
Sequence in context: A172316 A062258 A239560 * A122189 A194630 A251672
Adjacent sequences: A066175 A066176 A066177 * A066179 A066180 A066181


KEYWORD

nonn,easy


AUTHOR

Len Smiley, Dec 14 2001


EXTENSIONS

Definition corrected by Vincenzo Librandi, Dec 20 2010


STATUS

approved



