A122189 -id:A122189 - 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.

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

Len Smiley, Dec 14 2001

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

T. D. Noe, Table of n, a(n) for n = 0..200
Martin Burtscher, Igor Szczyrba, and 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, and 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
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
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).

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

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 *)

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

Definition corrected by Vincenzo Librandi, Dec 20 2010

A248700 Indices of primes in the Heptanacci numbers sequence A122189.

Original entry on oeis.org

8, 14, 22, 102495, 130447, 173590

Offset: 1

Robert Price, Dec 02 2014

a(7) > 2*10^5.

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

Cf. A001590, A001631, A100683, A231574, A231575, A232542, A214899, A230607, A020992, A232498, A214727, A081172, A214752, A141523, A214825, A235862, A000288, A000322, A122189.

a={0,0,0,0,0,0,1}; For[n=7, n<=1000, n++, sum=Plus@@a; If[PrimeQ[sum], Print[n]]; a=RotateLeft[a]; a[[7]]=sum]

A060455 7th-order Fibonacci numbers with a(0)=...=a(6)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193, 385, 769, 1531, 3049, 6073, 12097, 24097, 48001, 95617, 190465, 379399, 755749, 1505425, 2998753, 5973409, 11898817, 23702017, 47213569, 94047739, 187339729, 373174033, 743349313, 1480725217

Offset: 0

Frank Ellermann, Apr 08 2001

a(n) = number of runs in polyphase sort using 8 tapes and n-6 phases.

			General formula for k-th order numbers: f(n,k) = f(n-1,k) + ... + f(n-1-k,k) for n > k, otherwise f(n,k) = 1.

N. Wirth, Algorithmen und Datenstrukturen, 1975 (table 2.15 chapter 2.3.4).

Indranil Ghosh, Table of n, a(n) for n = 0..3339 (terms 0..200 from T. D. Noe)
R. L. Gilstad, Polyphase Merge Sort - Advanced Technique, Proc. AFIPS Eastern Jt. Comp. Conf. 18 (1960) 143-148.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

For k=1..5 see A000045, A000213, A000288, A000322, A000383.
Cf. A253333, A253318: primes and indices of primes in this sequence.
Cf. A122189 Heptanacci numbers with a(0),...,a(6) = 0,0,0,0,0,0,1.

m:=40; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(  (1-x^2-2*x^3-3*x^4-4*x^5-5*x^6)/(1-x-x^2-x^3-x^4-x^5-x^6-x^7) )); // G. C. Greubel, Feb 03 2019

A060455 := proc(n) option remember: if n >=0 and n<=6 then RETURN(1) fi: procname(n-1)+procname(n-2)+procname(n-3)+procname(n-4)+procname(n-5)+procname(n-6)+procname(n-7) end;

LinearRecurrence[{1,1,1,1,1,1,1},{1,1,1,1,1,1,1},40] (* Harvey P. Dale, Mar 17 2012 *)

Vec((1-x^2-2*x^3-3*x^4-4*x^5-5*x^6)/(1-x-x^2-x^3-x^4-x^5-x^6-x^7) +O(x^40)) \\ Charles R Greathouse IV, Feb 03 2014

((1-x^2-2*x^3-3*x^4-4*x^5-5*x^6)/(1-x-x^2-x^3-x^4-x^5-x^6-x^7) ).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Feb 03 2019

a(n) = a(n-1) + a(n-2) + ... + a(n-7) for n > 6, a(0)=a(1)=...=a(6)=1.

G.f.: (-1 + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 5*x^6)/(-1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7). - R. J. Mathar, Oct 11 2011

More terms from James Sellers, Apr 11 2001

A122265 10th-order Fibonacci numbers: a(n+1) = a(n)+...+a(n-9) with a(0) = ... = a(8) = 0, a(9) = 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172, 16336, 32656, 65280, 130496, 260864, 521472, 1042432, 2083841, 4165637, 8327186, 16646200, 33276064, 66519472, 132973664, 265816832, 531372800, 1062224128

Offset: 0

Roger L. Bagula and Gary W. Adamson, Oct 18 2006

nonn

The (1,10)-entry of the matrix M^n, where M is the 10 X 10 matrix {{0,1,0,0,0, 0,0,0,0,0},{0,0,1,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0, 0,0,0,1,0},{0,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}}.

Robert Price, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1,1,1).

Cf. A000322, A001591, A001592, A079262.
Cf. A001591, A001592, A122189, A079262, A104144, A168082, A168083, A168084. - Richard Choulet, Feb 22 2010
Cf. A257227, A257228 for primes in this sequence.

with(linalg): p:=-1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9+x^10: M[1]:=transpose(companion(p,x)): for n from 2 to 40 do M[n]:=multiply(M[n-1],M[1]) od: seq(M[n][1,10],n=1..40);
k:=10:for n from 0 to 50 do l(n):=sum((-1)^i*binomial(n-k+1-k*i,i)*2^(n-k+1-(k+1)*i),i=0..floor((n-k+1)/(k+1)))-sum((-1)^i*binomial(n-k-k*i,i)*2^(n-k-(k+1)*i),i=0..floor((n-k)/(k+1))):od:seq(l(n),n=0..50);k:=10:a:=taylor((z^(k-1)-z^(k))/(1-2*z+z^(k+1)),z=0,51);for p from 0 to 50 do j(p):=coeff(a,z,p):od :seq(j(p),p=0..50); # Richard Choulet, Feb 22 2010

M = {{0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}; v[1] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; v[n_] := v[n] = M.v[n - 1]; a = Table[Floor[v[n][[1]]], {n, 1, 50}]
a={1,0,0,0,0,0,0,0,0,0};Flatten[Prepend[Table[s=Plus@@a;a=RotateLeft[a];a[[ -1]]=s,{n,60}],Table[0,{m,Length[a]-1}]]] (* Vladimir Joseph Stephan Orlovsky, Nov 18 2009 *)
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 50]  (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
With[{nn=10},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* Harvey P. Dale, Aug 17 2013 *)

a(n) = Sum_{j=1..10} a(n-j) for n>=10; a(n) = 0 for 0<=n<=8, a(9) = 1 (follows from the minimal polynomial of M; a Maple program based on this recurrence relation is much slower than the given Maple program, based on the definition).
G.f.: -x^9/(-1+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
Another form of the g.f. f: f(z)=(z^(k-1)-z^(k))/(1-2*z+z^(k+1)) with k=10. Then a(n)=sum((-1)^i*binomial(n-k+1-k*i,i)*2^(n-k+1-(k+1)*i),i=0..floor((n-k+1)/(k+1)))-sum((-1)^i*binomial(n-k-k*i,i)*2^(n-k-(k+1)*i),i=0..floor((n-k)/(k+1))) with k=10 and sum(alpha(i),i=m..n)=0 for m>n. - Richard Choulet, Feb 22 2010

Edited by N. J. A. Sloane, Oct 29 2006 and Mar 05 2011

A168084 Fibonacci 13-step numbers.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8191, 16381, 32760, 65516, 131024, 262032, 524032, 1048000, 2095872, 4191488, 8382464, 16763904, 33525760, 67047424, 134086657, 268156933, 536281106, 1072496696

Offset: 1

Vladimir Joseph Stephan Orlovsky, Nov 18 2009

G. C. Greubel, Table of n, a(n) for n = 1..1000
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.
M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015) # 15.4.7.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1).

Cf. A000078, A001591, A001592, A122189, A079262, A168083.

k:=13:a:=taylor((z^(k-1)-z^(k))/(1-2*z+z^(k+1)),z=0,51);for p from 0 to 50 do j(p):=coeff(a,z,p):od :seq(j(p),p=0..50); k:=13:for n from 0 to 50 do l(n):=sum((-1)^i*binomial(n-k+1-k*i,i)*2^(n-k+1-(k+1)*i),i=0..floor((n-k+1)/(k+1)))-sum((-1)^i*binomial(n-k-k*i,i)*2^(n-k-(k+1)*i),i=0..floor((n-k)/(k+1))):od:seq(l(n),n=0..50); # Richard Choulet, Feb 22 2010

a={1,0,0,0,0,0,0,0,0,0,0,0,0};Flatten[Prepend[Table[s=Plus@@a;a=RotateLeft[a];a[[ -1]]=s,{n,60}],Table[0,{m,Length[a]-1}]]]
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 50]
With[{nn=13},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* Harvey P. Dale, Aug 17 2013 *)

Another form of the g.f. f: f(z)=(z^(k-1)-z^(k))/(1-2*z+z^(k+1)) with k=13. then a(n)=sum((-1)^i*binomial(n-k+1-k*i,i)*2^(n-k+1-(k+1)*i),i=0..floor((n-k+1)/(k+1)))-sum((-1)^i*binomial(n-k-k*i,i)*2^(n-k-(k+1)*i),i=0..floor((n-k)/(k+1))) with k=13 and convention sum(alpha(i),i=m..n)=0 for m>n. - Richard Choulet, Feb 22 2010

A251710 7-step Fibonacci sequence starting with (0,0,0,0,0,1,0).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 2, 4, 8, 16, 32, 63, 126, 251, 500, 996, 1984, 3952, 7872, 15681, 31236, 62221, 123942, 246888, 491792, 979632, 1951392, 3887103, 7742970, 15423719, 30723496, 61200104, 121908416, 242837200, 483723008, 963558913, 1919374856, 3823325993

Offset: 0

Arie Bos, Dec 07 2014

a(n+7) equals the number of n-length binary words avoiding runs of zeros of lengths 7i+6, (i=0,1,2,...). - Milan Janjic, Feb 26 2015

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Other 7-step Fibonacci sequences are A066178, A104621, A122189, A251711, A251712, A251713, A251714.

NB. see A251713 for the program and apply it to 0 0 0 0 0 1 0.

LinearRecurrence[Table[1, {7}], {0, 0, 0, 0, 0, 1, 0}, 40] (* Michael De Vlieger, Dec 09 2014 *)

a(n+7) = a(n) + a(n+1) + a(n+2) + a(n+3) + a(n+4) + a(n+5) + a(n+6).
G.f.: x^5*(x-1)/(-1+x+x^2+x^3+x^4+x^5+x^6+x^7) . - R. J. Mathar, Mar 28 2025
a(n) = A066178(n-5)-A066178(n-6). - R. J. Mathar, Mar 28 2025

A251711 7-step Fibonacci sequence starting with (0,0,0,0,1,0,0).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 2, 4, 8, 16, 31, 62, 124, 247, 492, 980, 1952, 3888, 7745, 15428, 30732, 61217, 121942, 242904, 483856, 963824, 1919903, 3824378, 7618024, 15174831, 30227720, 60212536, 119941216, 238918608, 475917313, 948010248, 1888402472, 3761630113

Offset: 0

Arie Bos, Dec 07 2014

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Other 7-step Fibonacci sequences are A066178, A104621, A122189, A251710, A251712, A251713, A251714.

NB. see A251713 for the program and apply it to 0 0 0 0 1 0 0.

LinearRecurrence[Table[1, {7}], {0, 0, 0, 0, 1, 0, 0}, 40] (* Michael De Vlieger, Dec 09 2014 *)

a(n+7) = a(n) + a(n+1) + a(n+2) + a(n+3) + a(n+4) + a(n+5) + a(n+6).
G.f.: x^4*(-1+x+x^2)/(-1+x+x^2+x^3+x^4+x^5+x^6+x^7) . - R. J. Mathar, Mar 28 2025
a(n) = A066178(n-4)-A066178(n-5)-A066178(n-6). - R. J. Mathar, Mar 28 2025

A251712 7-step Fibonacci sequence starting with (0,0,0,1,0,0,0).

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 2, 4, 8, 15, 30, 60, 120, 239, 476, 948, 1888, 3761, 7492, 14924, 29728, 59217, 117958, 234968, 468048, 932335, 1857178, 3699432, 7369136, 14679055, 29240152, 58245336, 116022624, 231112913, 460368648, 917037864, 1826706592, 3638734129

Offset: 0

Arie Bos, Dec 07 2014

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Other 7-step Fibonacci sequences are A066178, A104621, A122189, A251710, A251711, A251713, A251714.

NB. see A251713 for the program and apply it to 0 0 0 1 0 0 0.

LinearRecurrence[Table[1, {7}], {0, 0, 0, 1, 0, 0, 0}, 40] (* Michael De Vlieger, Dec 09 2014 *)

a(n+7) = a(n) + a(n+1) + a(n+2) + a(n+3) + a(n+4) + a(n+5) + a(n+6).

G.f.: x^3*(-1+x+x^2+x^3)/(-1+x+x^2+x^3+x^4+x^5+x^6+x^7) . - R. J. Mathar, Mar 28 2025

A251713 7-step Fibonacci sequence starting with (0,0,1,0,0,0,0).

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 1, 2, 4, 7, 14, 28, 56, 112, 223, 444, 884, 1761, 3508, 6988, 13920, 27728, 55233, 110022, 219160, 436559, 869610, 1732232, 3450544, 6873360, 13691487, 27272952, 54326744, 108216929, 215564248, 429396264, 855341984, 1703810608, 3393929729

Offset: 0

Arie Bos, Dec 07 2014

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Other 7-step Fibonacci sequences are A066178, A104621, A122189, A251710, A251711, A251712, A251714.

(see www.jsoftware.com) First construct the generating matrix
   [M=: (#.@}: + {:)\"1&.|: <:/~i.7
 1  1  1  1  1  1  1
 1  2  2  2  2  2  2
 2  3  4  4  4  4  4
 4  6  7  8  8  8  8
 8 12 14 15 16 16 16
16 24 28 30 31 32 32
32 48 56 60 62 63 64
Given that matrix, one can produce the first 7*150 numbers by
, M(+/ . *)^:(i.150) 0 0 1 0 0 0 0x

LinearRecurrence[Table[1, {7}], {0, 0, 1, 0, 0, 0, 0}, 40] (* Michael De Vlieger, Dec 09 2014 *)

a(n+7) = a(n) + a(n+1) + a(n+2) + a(n+3) + a(n+4) + a(n+5) + a(n+6).

G.f.: x^2*(-1+x+x^2+x^3+x^4)/(-1+x+x^2+x^3+x^4+x^5+x^6+x^7) . - R. J. Mathar, Mar 28 2025

A251714 7-step Fibonacci sequence starting with (0,1,0,0,0,0,0).

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 6, 12, 24, 48, 96, 191, 380, 757, 1508, 3004, 5984, 11920, 23744, 47297, 94214, 187671, 373834, 744664, 1483344, 2954768, 5885792, 11724287, 23354360, 46521049, 92668264, 184591864, 367700384, 732446000, 1459006208, 2906288129

Offset: 0

Arie Bos, Dec 07 2014

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Other 7-step Fibonacci sequences are A066178, A104621, A122189, A251710, A251711, A251712, A251713.

NB. see A251713 for the program and apply it to 0 1 0 0 0 0 0.

LinearRecurrence[Table[1, {7}], {0, 1, 0, 0, 0, 0, 0}, 40] (* Michael De Vlieger, Dec 09 2014 *)

a(n+7) = a(n) + a(n+1) + a(n+2) + a(n+3) + a(n+4) + a(n+5) + a(n+6).

G.f.: x*(-1+x+x^2+x^3+x^4+x^5)/(-1+x+x^2+x^3+x^4+x^5+x^6+x^7) . - R. J. Mathar, Mar 28 2025

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A248700 Indices of primes in the Heptanacci numbers sequence A122189.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A060455 7th-order Fibonacci numbers with a(0)=...=a(6)=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A122265 10th-order Fibonacci numbers: a(n+1) = a(n)+...+a(n-9) with a(0) = ... = a(8) = 0, a(9) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A168084 Fibonacci 13-step numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A251710 7-step Fibonacci sequence starting with (0,0,0,0,0,1,0).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

J

Mathematica

Formula

A251711 7-step Fibonacci sequence starting with (0,0,0,0,1,0,0).

Views

Author

Keywords

Links

Crossrefs

Programs

J

Mathematica