cp's OEIS Frontend

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

%I A066178 #63 Feb 16 2025 08:32:45
%S A066178 1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936,15808,31489,62725,
%T A066178 124946,248888,495776,987568,1967200,3918592,7805695,15548665,
%U A066178 30972384,61695880,122895984,244804400,487641600
%N A066178 Number of binary bit strings of length n with no block of 8 or more 0's. Nonzero heptanacci numbers, A122189.
%C A066178 Analogous bit string description and o.g.f. (1-x)/(1-2x+x^{k+1}) works for nonzero k-nacci numbers.
%C A066178 Compositions of n into parts <= 7. - _Joerg Arndt_, Aug 06 2012
%H A066178 T. D. Noe, <a href="/A066178/b066178.txt">Table of n, a(n) for n = 0..200</a>
%H A066178 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 A066178 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 A066178 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 A066178 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 A066178 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 A066178 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 A066178 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>
%H A066178 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HeptanacciNumber.html">Heptanacci Number</a>
%H A066178 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1,1,1,1).
%F A066178 O.g.f.: 1/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).
%F A066178 a(n) = Sum_{i=n-7..n-1} a(i).
%F A066178 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 A066178 a(n) = 2*a(n-1) - a(n-8). - _Vincenzo Librandi_, Dec 20 2010
%t A066178 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 A066178 CoefficientList[ Series[(1 - x)/(1 - 2 x + x^8), {x, 0, 30}], x]
%t A066178 LinearRecurrence[{1,1,1,1,1,1,1},{1,1,2,4,8,16,32},40] (* _Harvey P. Dale_, Nov 16 2014 *)
%Y A066178 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 A066178 Row 7 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
%K A066178 nonn,easy
%O A066178 0,3
%A A066178 _Len Smiley_, Dec 14 2001
%E A066178 Definition corrected by _Vincenzo Librandi_, Dec 20 2010