A192804 Constant term in the reduction of the polynomial 1+x+x^2+...+x^n by x^3->x^2+x+1. See Comments.

1, 1, 1, 2, 3, 5, 9, 16, 29, 53, 97, 178, 327, 601, 1105, 2032, 3737, 6873, 12641, 23250, 42763, 78653, 144665, 266080, 489397, 900141, 1655617, 3045154, 5600911, 10301681, 18947745, 34850336, 64099761, 117897841, 216847937, 398845538

Offset

0,4

Comments

For discussions of polynomial reduction, see A192232 and A192744.

This sequence provides the most-significant place-values in the construction of a tribonacci code. - James Dow Allen, Jul 12 2021

Links

Table of n, a(n) for n=0..35.

James Dow Allen, Constructing the Tribonacci Code.

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

Formula

a(n) = 2*a(n-1) - a(n-4).

a(n) = a(n-1) + a(n-2) + a(n-3) - 1. - Alzhekeyev Ascar M, Feb 05 2012

G.f.: ( 1-x-x^2 ) / ( (x-1)*(x^3+x^2+x-1) ). - R. J. Mathar, May 06 2014

a(n) - a(n-1) = A000073(n-1). - R. J. Mathar, May 06 2014

Example

The first five polynomials p(n,x) and their reductions:
  p(1,x)=1 -> 1,
  p(2,x)=x+1 -> x+1,
  p(3,x)=x^2+x+1 -> x^2+x+1,
  p(4,x)=x^3+x^2+x+1 -> 2x^2+2x+2,
  p(5,x)=x^4+x^3+x^2+x+1 -> 4x^2+4*x+3, so that
A192804=(1,1,1,2,3,...), A000073=(0,1,1,2,4,...), A008937=(0,0,1,2,4,...).

Mathematica

q = x^3; s = x^2 + x + 1; z = 40;
p[0, x_] := 1; p[n_, x_] := x^n + p[n - 1, x];
Table[Expand[p[n, x]], {n, 0, 7}]
reduce[{p1_, q_, s_, x_}] :=
FixedPoint[(s PolynomialQuotient @@ #1 +
       PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]
t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]
  (* A192804 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A000073 *)
u3 = Table[Coefficient[Part[t, n], x, 2], {n, 1, z}]
  (* A008937 *)

Crossrefs

Cf. A192744, A192232, A000073.

Sequence in context: A054650 A022857 A000691 * A255071 A103285 A000049

Adjacent sequences: A192801 A192802 A192803 * A192805 A192806 A192807

Keyword

nonn,easy

Author

Clark Kimberling, Jul 10 2011

Status

approved