A073817 -id:A073817 - cp's OEIS frontend

A000078 Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n >= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533, 28074040, 54114452, 104308960, 201061985, 387559437, 747044834, 1439975216, 2775641472

Offset: 0

N. J. A. Sloane

a(n) is the number of compositions of n-3 with no part greater than 4. Example: a(7) = 8 because we have 1+1+1+1 = 2+1+1 = 1+2+1 = 3+1 = 1+1+2 = 2+2 = 1+3 = 4. - Emeric Deutsch, Mar 10 2004
In other words, a(n) is the number of ways of putting stamps in one row on an envelope using stamps of denominations 1, 2, 3 and 4 cents so as to total n-3 cents [Pólya-Szegő]. - N. J. A. Sloane, Jul 28 2012
a(n+4) is the number of 0-1 sequences of length n that avoid 1111. - David Callan, Jul 19 2004
a(n) is the number of matchings in the graph obtained by a zig-zag triangulation of a convex (n-3)-gon. Example: a(8) = 15 because in the triangulation of the convex pentagon ABCDEA with diagonals AD and AC we have 15 matchings: the empty set, seven singletons and {AB,CD}, {AB,DE}, {BC,AD}, {BC,DE}, {BC,EA}, {CD,EA} and {DE,AC}. - Emeric Deutsch, Dec 25 2004
Number of permutations satisfying -k <= p(i)-i <= r, i=1..n-3, with k = 1, r = 3. - Vladimir Baltic, Jan 17 2005
For n >= 0, a(n+4) is the number of palindromic compositions of 2*n+1 into an odd number of parts that are not multiples of 4. In addition, a(n+4) is also the number of Sommerville symmetric cyclic compositions (= bilaterally symmetric cyclic compositions) of 2*n+1 into an odd number of parts that are not multiples of 4. - Petros Hadjicostas, Mar 10 2018
a(n) is the number of ways to tile a hexagonal double-strip (two rows of adjacent hexagons) containing (n-4) cells with hexagons and double-hexagons (two adjacent hexagons). - Ziqian Jin, Jul 28 2019
The term "tetranacci number" was coined by Mark Feinberg (1963; see A000073). - Amiram Eldar, Apr 16 2021
a(n) is the number of ways to tile a skew double-strip of n-3 cells using squares and all possible "dominos", as seen in Ziqian Jin's article, below. Here is the skew double-strip corresponding to n=15, with 12 cells:
   _ ___ _ ___ _ ___
  |   |   |   |   |   |   |
 |__|___|_|___| |___|
|   |   |   |   |   |   |
|_|___|_|___|_|___|,
and here are the three possible "domino" tiles:
   _     _
  |   |   |   |
 |  |   |  |      _____
|   |       |   |    |       |
|_|,      |_|,   |_____|.
As an example, here is one of the a(15) = 1490 ways to tile the skew double-strip of 12 cells:
   _ ___ _____ _______
  |   |   |   |   |   |   |
 |__|_  |_|_ | _|  _|
|       |   |   |   |   |
|_____|___|_|___|_|. - Greg Dresden, Jun 05 2024

			From _Petros Hadjicostas_, Mar 10 2018: (Start)
For n = 3, we get a(3+4) = a(7) = 8 palindromic compositions of 2*n+1 = 7 into an odd number of parts that are not a multiple of 4. They are the following: 7 = 1+5+1 = 3+1+3 = 2+3+2 = 1+2+1+2+1 = 2+1+1+1+2 = 1+1+3+1+1 = 1+1+1+1+1+1+1. If we put these compositions on a circle, they become bilaterally symmetric cyclic compositions of 2*n+1 = 7.
For n = 4, we get a(4+4) = a(8) = 15 palindromic compositions of 2*n + 1 = 9 into an odd number of parts that are not a multiple of 4. They are the following: 9 = 3+3+3 = 2+5+2 = 1+7+1 = 1+1+5+1+1 = 2+1+3+1+2 = 1+2+3+2+1 = 1+3+1+3+1 = 3+1+1+1+3 = 2+2+1+2+2 = 2+1+1+1+1+1+2 = 1+2+1+1+1+2+1 = 1+1+2+1+2+1+1 = 1+1+1+3+1+1+1 = 1+1+1+1+1+1+1+1+1.
As _David Callan_ points out in the comments above, for n >= 1, a(n+4) is also the number of 0-1 sequences of length n that avoid 1111. For example, for n = 5, a(5+4) = a(9) = 29 is the number of binary strings of length n that avoid 1111. Out of the 2^5 = 32 binary strings of length n = 5, the following do not avoid 1111: 11111, 01111, and 11110. (End)

Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1, Problems 3 and 4.
J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 0..3505 (terms 0..200 from T. D. Noe)
Abdullah Açikel, Amrouche Said, Hacene Belbachir, and Nurettin Irmak, On k-generalized Lucas sequence with its triangle, Turkish J. Math. (2023) Vol. 47, No. 4, Art. 6, 1129-1143. See p. 1130.
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Tomás Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Martínez Mori, Casandra D. Monroe, Daniel Quiñonez, Dirk Tolson III, and Dwight Anderson Williams II, Interval and L-interval Rational Parking Functions, arXiv:2311.14055 [math.CO], 2023.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 2, 6, 8.
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 307-309.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4(1) (2010), 119-135.
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 2.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, J. Integer Seq. 18 (2015), Article 15.4.5.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integer Seq. 3 (2000), Article 00.1.5.
S. A. Corey and Otto Dunkel, Problem 2803, Amer. Math. Monthly 33 (1926), 229-232.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, J. Integer Seq. 19 (2016), Article 16.1.1.
Emeric Deutsch, Problem 1613: A recursion in four parts, Math. Mag. 75(1) (2002), 64-65.
Ömür Deveci, Zafer Adıgüzel and Taha Doğan, On the Generalized Fibonacci-circulant-Hurwitz numbers, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.
G. P. B. Dresden and Z. Du, A Simplified Binet Formula for k-Generalized Fibonacci Numbers, J. Integer Seq. 17 (2014), Article 14.4.7.
M. Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(3) (1963), 71-74.
Taras Goy and Mark Shattuck, Some Toeplitz-Hessenberg determinant identities for the tetranacci numbers, J. Integer Seq. 23 (2020), Article 20.6.8.
Petros Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Seq. 19 (2016), Article 16.8.2.
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
P. Hadjicostas and L. Zhang, Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer, Fibonacci Quarterly 55 (2017), 54-73.
Russell Jay Hendel, A Method for Uniformly Proving a Family of Identities, arXiv:2107.03549 [math.CO], 2021.
F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quarterly 49 (2011), 231-242.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 11
Ziqian Jin, Tetrancci Identities With Squares, Dominoes, And Hexagonal Double Strips, arXiv:1907.09935 [math.GM], 2019.
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.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
W. C. Lynch, The t-Fibonacci numbers and polyphase sorting, Fib. Quart., 8 (1970), 6-22.
T. Mansour and M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv:1410.6943 [math.CO], 2014.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. Integer Seq. 8 (2005), Article 05.4.4.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
H. Prodinger, Counting Palindromes According to r-Runs of Ones Using Generating Functions, J. Integer Seq. 17 (2014), Article 14.6.2; odd length middle 0, r=3.
Helmut Prodinger and Sarah J. Selkirk, Sums of squares of Tetranacci numbers: A generating function approach, arXiv:1906.08336 [math.NT], 2019.
Lan Qi and Zhuoyu Chen, Identities Involving the Fourth-Order Linear Recurrence Sequence, Symmetry 11(12) (2019), 1476, 8pp.
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, Electron. J. Combin. 22(1) (2015), #P1.38.
O. Turek, Abelian Complexity Function of the Tribonacci Word, J. Integer Seq. 18 (2015), Article 15.3.4.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Eric Weisstein's World of Mathematics, Tetranacci Number.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).

Row 4 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
First differences are in A001631.
Cf. A008287 (quadrinomial coefficients) and A073817 (tetranacci with different initial conditions).

a:=[0,0,0,1];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]+a[n-4]; od; a; # Muniru A Asiru, Mar 11 2018

import Data.List (tails, transpose)
a000078 n = a000078_list !! n
a000078_list = 0 : 0 : 0 : f [0,0,0,1] where
   f xs = y : f (y:xs) where
     y = sum $ head $ transpose $ take 4 $ tails xs
-- Reinhard Zumkeller, Jul 06 2014, Apr 28 2011

[n le 4 select Floor(n/4) else Self(n-1)+Self(n-2)+Self(n-3)+Self(n-4): n in [1..50]]; // Vincenzo Librandi, Jan 29 2016

a:= n-> (<<1|1|0|0>, <1|0|1|0>, <1|0|0|1>, <1|0|0|0>>^n)[1, 4]: seq(a(n), n=0..50); # Alois P. Heinz, Jun 12 2008

CoefficientList[Series[x^3/(1-x-x^2-x^3-x^4), {x, 0, 50}], x]
LinearRecurrence[{1,1,1,1}, {0,0,0,1}, 50]  (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
(* From Eric W. Weisstein, Nov 09 2017 *)
Table[RootSum[-1 -# -#^2 -#^3 +#^4 &, 10#^n +157#^(n+1) -103 #^(n+2) +16#^(n+3) &]/563, {n, 0, 40}]
Table[RootSum[#^4 -#^3 -#^2 -# -1 &, #^(n-2)/(-#^3 +6# -1) &], {n, 0, 40}] (* End *)

a(n):=sum(sum(if mod(5*k-i,4)>0 then 0 else binomial(k,(5*k-i)/4)*(-1)^((i-k)/4)*binomial(n-i+k-1,k-1),i,k,n),k,1,n); /* Vladimir Kruchinin, Aug 18 2010 */

{a(n) = if( n<0, 0, polcoeff( x^3 / (1 - x - x^2 - x^3 - x^4) + x * O(x^n), n))}

A000078 = [0,0,0,1]
for n in range(4, 100):
    A000078.append(A000078[n-1]+A000078[n-2]+A000078[n-3]+A000078[n-4])
# Chai Wah Wu, Aug 20 2014

a(n) = A001630(n) - a(n-1). - Henry Bottomley
G.f.: x^3/(1 - x - x^2 - x^3 - x^4). - Simon Plouffe in his 1992 dissertation
G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - Michael Somos, May 12 2012
G.f.: Sum_{n >= 0} x^(n+3) * (Product_{k = 1..n} (k + k*x + k*x^2 + x^3)/(1 + k*x + k*x^2 + k*x^3)). - Peter Bala, Jan 04 2015
a(n) = term (1,4) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,1; 1,0,0,0]^n. - Alois P. Heinz, Jun 12 2008
Another form of the g.f.: f(z) = (z^3 - z^4)/(1 - 2*z + z^5), then a(n) = Sum_{i=0..floor((n-3)/5)} (-1)^i*binomial(n-3-4*i, i)*2^(n - 3 - 5*i) - Sum_{i=0..floor((n-4)/5)} (-1)^i*binomial(n-4-4*i, i)*2^(n - 4 - 5*i) with natural convention Sum_{i=m..n} alpha(i) = 0 for m > n. - Richard Choulet, Feb 22 2010
a(n+3) = Sum_{k=1..n} Sum_{i=k..n} [(5*k-i mod 4) = 0] * binomial(k, (5*k-i)/4) *(-1)^((i-k)/4) * binomial(n-i+k-1,k-1), n > 0. - Vladimir Kruchinin, Aug 18 2010 [Edited by Petros Hadjicostas, Jul 26 2020, so that the formula agrees with the offset of the sequence]
Sum_{k=0..3*n} a(k+b) * A008287(n,k) = a(4*n+b), b >= 0 ("quadrinomial transform"). - N. J. A. Sloane, Nov 10 2010
G.f.: x^3*(1 + x*(G(0)-1)/(x+1)) where G(k) = 1 + (1+x+x^2+x^3)/(1-x/(x+1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 26 2013
Starting (1, 2, 4, 8, ...) = the INVERT transform of (1, 1, 1, 1, 0, 0, 0, ...). - Gary W. Adamson, May 13 2013
a(n) ~ c*r^n, where c = 0.079077767399388561146007... and r = 1.92756197548292530426195... = A086088 (One of the roots of the g.f. denominator polynomial is 1/r.). - Fung Lam, Apr 29 2014
a(n) = 2*a(n-1) - a(n-5), n >= 5. - Bob Selcoe, Jul 06 2014
From Ziqian Jin, Jul 28 2019: (Start)
a(2*n+5) = a(n+4)^2 + a(n+3)^2 + a(n+2)^2 + 2*a(n+3)*(a(n+2) + a(n+1)).
a(n) - 1 = a(n-2) + 2*a(n-3) + 3*(a(n-4) + a(n-5) + ... + a(2) + a(1)), n >= 4. (End)
a(n) = (Sum_{i=0..n-1} a(i)*A073817(n-i))/(n-3) for n > 3. - Greg Dresden and Advika Srivastava, Sep 28 2019
a(n) = Sum_{r root of x^4-x^3-x^2-x-1} r^n/(4*r^3-3*r^2-2*r-1). - Fabian Pereyra, Dec 06 2024

Definition augmented (with 4 initial terms) by Daniel Forgues, Dec 02 2009

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15.

Original entry on oeis.org

5, 1, 3, 7, 15, 31, 57, 113, 223, 439, 863, 1695, 3333, 6553, 12883, 25327, 49791, 97887, 192441, 378329, 743775, 1462223, 2874655, 5651423, 11110405, 21842481, 42941187, 84420151, 165965647, 326279871, 641449337, 1261056193, 2479171199, 4873922247

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Aug 14 2002

These pentanacci numbers follow the same pattern as Lucas, generalized tribonacci(A001644) and generalized tetranacci (A073817) numbers: Binet's formula is a(n)=r1^n+r^2^n+r3^n+r4^n+r5^n, with r1, r2, r3, r4, r5 roots of the characteristic polynomial. a(n) is also the trace of A^n, where A is the pentamatrix ((1,1,0,0,0),(1,0,1,0,0),(1,0,0,1,0),(1,0,0,0,1),(1,0,0,0,0)).
For n >= 5, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain five consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). (For n=1,2,3,4 the statement is still true provided we allow the sequence to wrap around itself on a circle). - Petros Hadjicostas, Dec 18 2016
a(3407) has 1001 decimal digits. - Michael De Vlieger, Dec 28 2016

Michael De Vlieger, Table of n, a(n) for n = 0..3406
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.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
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.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
S. Saito, T. Tanaka, and N. Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, Journal of Integer Sequences, 14 (2011), # 11.2.4, Table 3.
Yüksel Soykan, On A Generalized Pentanacci Sequence, Asian Research Journal of Mathematics (2019) Vol. 14, No. 3, 1-9.
Yüksel Soykan, Sum Formulas for Generalized Fifth-Order Linear Recurrence Sequences, Journal of Advances in Mathematics and Computer Science (2019) Vol. 34, No. 5, 1-14.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A073817, A106297 (Pisano Periods).
Essentially the same as A023424.
Cf. A123126, A123127, A074062.
Cf. A106273.

CoefficientList[Series[(5-4*x-3*x^2-2*x^3-x^4)/(1-x-x^2-x^3-x^4-x^5), {x, 0, 30}], x]
LinearRecurrence[{1, 1, 1, 1, 1}, {5, 1, 3, 7, 15}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

polsym(polrecip(1-x-x^2-x^3-x^4-x^5),33) \\ Joerg Arndt, Jan 28 2019

a(n) = a(n-1) +a(n-2) +a(n-3) +a(n-4) +a(n-5).
G.f.: (5-4*x-3*x^2-2*x^3-x^4) / (1-x-x^2-x^3-x^4-x^5).
a(n) = 2*a(n-1) -a(n-6), n>5. [Vincenzo Librandi, Dec 20 2010]
For k>0 and n>=0, a(n+5*k) = a(k)*a(n+4*k) - A123127(k-1)*a(n+3*k) + A123126(k-1)*a(n+2*k) - A074062(k)*a(n+k) + a(n). For example, if k=4, n=3, we have a(n+5*k) = a(23) = 5651423, a(4)*a(19) - A123127(3)*a(15) + A123126(3)*a(1695) - A074062(4)*a(7) + a(3) = (15)*(378329) - (1)*(25327) + (1)*(1695) - (-1)*(113) + (7) = 5651423. - Kai Wang, Sep 13 2020
From Kai Wang, Dec 16 2020: (Start)
For k >= 0,
    | a(k+4) a(k+5) a(k+6) a(k+7) a(k+8) |
    | a(k+3) a(k+4) a(k+5) a(k+6) a(k+7) |
det | a(k+2) a(k+3) a(k+4) a(k+5) a(k+6) | = 9584 = A106273(5).
    | a(k+1) a(k+2) a(k+3) a(k+4) a(k+5) |
    | a(k)   a(k+1) a(k+2) a(k+3) a(k+4) |
(End)

A074584 Esanacci (hexanacci or "6-anacci") numbers.

Original entry on oeis.org

6, 1, 3, 7, 15, 31, 63, 120, 239, 475, 943, 1871, 3711, 7359, 14598, 28957, 57439, 113935, 225999, 448287, 889215, 1763832, 3498707, 6939975, 13766015, 27306031, 54163775, 107438335, 213112838, 422726969, 838513963, 1663261911, 3299217791, 6544271807

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Aug 26 2002

These esanacci numbers follow the same pattern as Lucas, generalized tribonacci (A001644), generalized tetranacci (A073817), and generalized pentanacci (A074048) numbers.
The closed form is a(n) = r1^n + r^2^n + r3^n + r4^n + r5^n + r6^n, with r1, r2, r3, r4, r5, r6 roots of the characteristic polynomial.
a(n) is also the trace of A^n, where A is the matrix ((1, 1, 0, 0, 0, 0), (1, 0, 1, 0, 0, 0), (1, 0, 0, 1, 0, 0), (1, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 1), (1, 0, 0, 0, 0, 0)).

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.
Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math/0210201 [math.CO], 2002.
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.
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.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A073817, A074048.

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

CoefficientList[Series[(6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6), {x, 0, 40}], x]
LinearRecurrence[{1,1,1,1,1,1},{6,1,3,7,15,31},40] (* Harvey P. Dale, Nov 08 2011 *)

polsym(polrecip(1-x-x^2-x^3-x^4-x^5-x^6), 40) \\ G. C. Greubel, Apr 22 2019

def aupton(nn):
  alst = [6, 1, 3, 7, 15, 31]
  for n in range(6, nn+1): alst.append(sum(alst[n-6:n]))
  return alst[:nn+1]
print(aupton(33)) # Michael S. Branicky, Jun 01 2021

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

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) + a(n-6), a(0)=6, a(1)=1, a(2)=3, a(3)=7, a(4)=15, a(5)=31.
G.f.: (6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6).
a(n) = 2*a(n-1) - a(n-7) for n >= 7. - Vincenzo Librandi, Dec 20 2010

A104621 Heptanacci-Lucas numbers.

Original entry on oeis.org

7, 1, 3, 7, 15, 31, 63, 127, 247, 493, 983, 1959, 3903, 7775, 15487, 30847, 61447, 122401, 243819, 485679, 967455, 1927135, 3838783, 7646719, 15231991, 30341581, 60439343, 120393007, 239818559, 477709983, 951581183, 1895515647, 3775799303, 7521257025

Offset: 0

Jonathan Vos Post, Mar 17 2005

This 7th-order linear recurrence is a generalization of the Lucas sequence A000032. Mario Catalani would refer to this is a generalized heptanacci sequence, had he not stopped his series of sequences after A001644 "generalized tribonacci", A073817 "generalized tetranacci", A074048 "generalized pentanacci", A074584 "generalized hexanacci." T. D. Noe and I have noted that each of these has many more primes than the corresponding tribonacci A000073 (see A104576), tetranacci A000288 (see A104577), pentanacci, hexanacci and heptanacci (see A104414). For primes in Heptanacci-Lucas numbers, see A104622. For semiprimes in Heptanacci-Lucas numbers, see A104623.

G. C. Greubel, Table of n, a(n) for n = 0..3300 (terms 0..200 from T. D. Noe)
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.
Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math/0210201 [math.CO], 2002.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
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.
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
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104414, A104576, A104577.

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

A104621 := proc(n)
    option remember;
    if n <=6 then
        op(n+1,[7, 1, 3, 7, 15, 31, 63])
    else
        add(procname(n-i),i=1..7) ;
    end if;
end proc: # R. J. Mathar, Mar 26 2015

a[0]=7; a[1]=1; a[2]=3; a[3]=7; a[4]=15; a[5]=31; a[6]=63; a[n_]:= a[n]= a[n-1]+a[n-2]+a[n-3]+a[n-4]+a[n-5]+a[n-6]+a[n-7]; Table[a[n], {n,0,40}] (* Robert G. Wilson v, Mar 17 2005 *)
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1}, {7, 1, 3, 7, 15, 31, 63}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

my(x='x+O('x^40)); Vec((-7+6*x+5*x^2+4*x^3+3*x^4+2*x^5+x^6)/(-1+x +x^2+x^3+x^4+x^5+x^6+x^7)) \\ G. C. Greubel, Dec 18 2017

polsym(polrecip(1-x-x^2-x^3-x^4-x^5-x^6-x^7), 40) \\ G. C. Greubel, Apr 22 2019

((-7+6*x+5*x^2+4*x^3+3*x^4+2*x^5+x^6)/(-1+x +x^2+x^3+x^4+x^5+x^6 +x^7)).series(x, 41).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) + a(n-6) + a(n-7); a(0) = 7, a(1) = 1, a(2) = 3, a(3) = 7, a(4) = 15, a(5) = 31, a(6) = 63.
From R. J. Mathar, Nov 16 2007: (Start)
G.f.: (7 - 6*x - 5*x^2 - 4*x^3 - 3*x^4 - 2*x^5 - x^6)/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).
a(n) = 7*A066178(n) - 6*A066178(n-1) - 5*A066178(n-2) - ... - 2*A066178(n-5) - A066178(n-6) if n >= 6. (End)

A105754 Lucas 8-step numbers.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 255, 502, 1003, 2003, 3999, 7983, 15935, 31807, 63487, 126719, 252936, 504869, 1007735, 2011471, 4014959, 8013983, 15996159, 31928831, 63730943, 127208950, 253913031, 506818327, 1011625183, 2019235407

Offset: 1

T. D. Noe, Apr 22 2005

G. C. Greubel, Table of n, a(n) for n = 1..2500 (terms 1..200 from T. D. Noe)
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.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
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.
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, Lucas n-Step Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104621, A105755 (Lucas n-step numbers).

a={-1, -1, -1, -1, -1, -1, -1, 8}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]
CoefficientList[Series[-x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8)/(-1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9), {x, 0, 50}], x] (* G. C. Greubel, Dec 18 2017 *)

a(n)=([0,1,0,0,0,0,0,0; 0,0,1,0,0,0,0,0; 0,0,0,1,0,0,0,0; 0,0,0,0,1,0,0,0; 0,0,0,0,0,1,0,0; 0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1]^(n-1)*[1;3;7;15;31;63;127;255])[1,1] \\ Charles R Greathouse IV, Jun 14 2015

x='x+O('x^30); Vec(-x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8)/(-1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)) \\ G. C. Greubel, Dec 18 2017

a(n) = Sum_{k=1..8} a(n-k) for n > 0, a(0)=8, a(n)=-1 for n=-7..-1.

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

A105755 Lucas 9-step numbers.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 255, 511, 1013, 2025, 4047, 8087, 16159, 32287, 64511, 128895, 257535, 514559, 1028105, 2054185, 4104323, 8200559, 16384959, 32737631, 65410751, 130692607, 261127679, 521740799, 1042453493, 2082852801

Offset: 1

T. D. Noe, Apr 22 2005

G. C. Greubel, Table of n, a(n) for n = 1..2500 (terms 1..200 from T. D. Noe)
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.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
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, Lucas n-Step Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104621, A105754 (Lucas n-step numbers).

a={-1, -1, -1, -1, -1, -1, -1, -1, 9}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]

a(n):=n*sum(sum((-1)^i*binomial(k,k-i)*binomial(n-9*i-1,k-1),i,0,(n-k)/9)/k,k,1,n);
makelist(a(n),n,1,17); /* Vladimir Kruchinin, Aug 10 2011 */

a(n)=([0,1,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0; 0,0,0,0,1,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1,1]^(n-1)*[1;3;7;15;31;63;127;255;511])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

a(n) = Sum_{k=1..9} a(n-k) for n > 0, a(0)=9, a(n)=-1 for n=-8..-1
G.f.: -x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8) / ( -1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 ). - R. J. Mathar, Jun 20 2011
a(n) = n*Sum_{k=1..n} (Sum_{i=0..floor((n-k)/9)} (-1)^i*binomial(k, k-i)*binomial(n-9*i-1, k-1))/k. - Vladimir Kruchinin, Aug 10 2011

A106273 Discriminant of the polynomial x^n - x^(n-1) - ... - x - 1.

Original entry on oeis.org

1, 5, -44, -563, 9584, 205937, -5390272, -167398247, 6042477824, 249317139869, -11597205023744, -601139006326619, 34383289858207744, 2151954708695291177, -146323302326154543104, -10742330662077208945103, 846940331265064719417344, 71373256668946058057974997

Offset: 1

T. D. Noe, May 02 2005

sign

This polynomial is the characteristic polynomial of the Fibonacci and Lucas n-step sequences. These discriminants are prime for n=2, 4, 6, 26, 158 (A106274). It appears that the term a(2n+1) always has a factor of 2^(2n). With that factor removed, the discriminants are prime for odd n=3, 5, 7, 21, 99, 405. See A106275 for the combined list.
a(n) is the determinant of an r X r Hankel matrix whose entries are w(i+j) where w(n) = x1^n + x2^n + ... + xr^n where x1,x2,...xr are the roots of the titular characteristic polynomial. E.g., A000032 for n=2, A001644 for n=3, A073817 for n=4, A074048 for n=5, A074584 for n=6, A104621 for n=7, ... - Kai Wang, Jan 17 2021
Luca proves that a(n) is a term of the corresponding k-nacci sequence only for n=2 and 3. - Michel Marcus, Apr 12 2025

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Mohammad K. Azarian, On the Hyperfactorial Function, Hypertriangular Function, and the Discriminants of Certain Polynomials, International Journal of Pure and Applied Mathematics 36(2), 2007, pp. 251-257. MR2312537. Zbl 1133.11012.
Michael Baake and Uwe Grimm, Fourier transform of Rauzy fractals and point spectrum of 1D Pisot inflation tilings, arXiv:1907.11012 [math.MG], 2019.
Herbert Batte and Florian Luca, The Discriminant of the Characteristic Polynomial of the kth Fibonacci sequence is not a member of the kth Lucas sequence, arXiv:2504.02514 [math.NT], 2025.
Florian Luca, On the discriminant of the k-generalized Fibonacci polynomial, II, Fibonacci Quart. 62 (2024), no. 3, 193-200.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Polynomial Discriminant

Cf. A086797 (discriminant of the polynomial x^n-x-1), A000045, A000073, A000078, A001591, A001592 (Fibonacci n-step sequences), A000032, A001644, A073817, A074048, A074584, A104621, A105754, A105755 (Lucas n-step sequences), A086937, A106276, A106277, A106278 (number of distinct zeros of these polynomials for n=2, 3, 4, 5).

Discriminant[p_?PolynomialQ, x_] := With[{n=Exponent[p, x]}, Cancel[((-1)^(n(n-1)/2) Resultant[p, D[p, x], x])/Coefficient[p, x, n]^(2n-1)]]; Table[Discriminant[x^n-Sum[x^i, {i, 0, n-1}], x], {n, 20}]

{a(n)=(-1)^(n*(n+1)/2)*((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2}  \\ Max Alekseyev, May 05 2005

a(n)=poldisc('x^n-sum(k=0,n-1,'x^k)); \\ Joerg Arndt, May 04 2013

a(n) = (-1)^(n*(n+1)/2) * ((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2. - Max Alekseyev, May 05 2005

cp's OEIS Frontend

A105763 Prime Lucas 4-step numbers, A073817.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A000078 Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n >= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Python

Formula

Extensions

A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A074584 Esanacci (hexanacci or "6-anacci") numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Sage

Formula

A104621 Heptanacci-Lucas numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A105754 Lucas 8-step numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula