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

%I #62 Sep 29 2024 04:33:05

%S 1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936,15808,31489,62725,

%T 124946,248888,495776,987568,1967200,3918592,7805695,15548665,

%U 30972384,61695880,122895984,244804400,487641600

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

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

%C Compositions of n into parts <= 7. - _Joerg Arndt_, Aug 06 2012

%H T. D. Noe, <a href="/A066178/b066178.txt">Table of n, a(n) for n = 0..200</a>

%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.pdf">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

%H Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, <a href="https://doi.org/10.3390/math8091487">An Alternating Sum of Fibonacci and Lucas Numbers of Order k</a>, Mathematics (2020) Vol. 9, 1487.

%H Zhao Hui Du, <a href="http://bbs.emath.ac.cn/viewthread.php?tid=667&amp;page=4&amp;fromuid=20#pid9145">Link giving derivation and proof of the formula</a>

%H Omar Khadir, László Németh, and László Szalay, <a href="https://doi.org/10.1007/s00025-024-02284-3">Tiling of dominoes with ranked colors</a>, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.

%H László Németh and László Szalay, <a href="https://arxiv.org/abs/2408.12196">Explicit solution of system of two higher-order recurrences</a>, arXiv:2408.12196 [math.NT], 2024. See p. 10.

%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HeptanacciNumber.html">Heptanacci Number</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1,1,1,1).

%F O.g.f.: 1/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).

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

%F 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

%F a(n) = 2*a(n-1) - a(n-8). - _Vincenzo Librandi_, Dec 20 2010

%t 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]

%t CoefficientList[ Series[(1 - x)/(1 - 2 x + x^8), {x, 0, 30}], x]

%t LinearRecurrence[{1,1,1,1,1,1,1},{1,1,2,4,8,16,32},40] (* _Harvey P. Dale_, Nov 16 2014 *)

%Y 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).

%Y Row 7 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

%K nonn,easy

%O 0,3

%A _Len Smiley_, Dec 14 2001

%E Definition corrected by _Vincenzo Librandi_, Dec 20 2010