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

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

Offset

0,3

Comments

Analogous bit string description and o.g.f. (1-x)/(1-2x+x^{k+1}) works for nonzero k-nacci numbers.

Compositions of n into 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 n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

Spiros D. Dafnis, Andreas N. Philippou, Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.

Zhao Hui Du, Link giving derivation and proof of the formula

Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4

Eric Weisstein's World of Mathematics, Fibonacci n-Step 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/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).

a(n) = Sum_{i=n-7..n-1} a(i).

a(n) = round((r-1)/((t+1)*r - 2*t) * r^(n-1)), where r is the heptanacci constant, the real root of the equation x^(t+1) - 2*x^t + 1 = 0 which is greater than 1. The formula could also be used for a k-step Fibonacci sequence if r is replaced by the k-bonacci constant, as in A000045, A000073, A000078, A001591, A001592. - Zhao Hui Du, Aug 24 2008

a(n) = 2*a(n-1) - a(n-8). - 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 (k-generalized 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