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

Author

Clark Kimberling, Jul 10 2011

Keywords

• nonn
• easy

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

Examples

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

Links

• James Dow Allen, Constructing the Tribonacci Code.
• Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Crossrefs

Cf. A192744, A192232, A000073.

Programs

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

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