A022319 -id:A022319 - cp's OEIS frontend

A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

1, 1, 3, 8, 29, 133, 762, 5215, 41257, 369032, 3676209, 40333241, 483094250, 6271446691, 87705811341, 1314473334832, 21017294666173, 357096406209005, 6424799978507178, 122024623087820183, 2439706330834135361, 51219771117454755544

Offset: 0

Clark Kimberling, Jul 09 2011

nonn

The titular polynomial is defined recursively by p(n,x)=x*p(n-1,x)+n! for n>0, where p(0,x)=1; see the Example.  For an introduction to polynomial reduction, see A192232.  The discussion at A192232 Comments continues here:
...
Let R(p,q,s) denote the "reduction of polynomial p by q->s" as defined at A192232.  Suppose that q(x)=x^k for some k>0 and that s(x)=s(k,0)*x^(k-1)+s(k,1)*x^(k-2)+...+s(k,k-2)x+s(k,k-1).
...
First, we shall take p(x)=x^n, where n>=0; the results will be used to formulate R(p,q,s) for general p.  Represent R(x^n,q,s) by
...
R(x^n)=s(n,0)*x^(k-1)+s(n,1)*x^(k-2)+...+s(n,k-2)*x+s(n,k-1).
...
Then each of the sequences u(n)=s(n,h), for h=0,1,...,k-1, satisfies this linear recurrence relation:
...
u(n)=s(k,0)*u(n-1)+s(k,1)*u(n-2)+...+s(k,k-2)*u(n-k-1)+s(k,k-1)*u(n-k), with initial values tabulated here:
...
n: ..s(n,0)...s(n,1)..s(n,2).......s(n,k-2)..s(n,k-1)
0: ....0........0.......0..............0.......1
1: ....0........0.......0..............1.......0
...
k-2: ..0........1.......0..............0.......0
k-1: ..0........0.......0..............0.......0
k: ..s(k,0)...s(k,1)..s(k,2).......s(k,k-2)..s(k,k-1)
...
That completes the formulation for p(x)=x^n.  Turning to the general case, suppose that
...
p(n,x)=p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n-1)*x+p(n,n)
...
is a polynomial of degree n>=0.  Then the reduction denoted by (R(p(n,x) by x^k -> s(x)) is the polynomial of degree k-1 given by the matrix product P*S*X, where P=(p(n,0)...p(n,1).........p(n-k)...p(n,n-k+1); X has all 0's except for main diagonal (x^(k-1), x^(k-2)...x,1); and S has
...
row 1: ... s(n,0) ... s(n,1) ...... s(n,k-2) . s(n,k-1)
row 2: ... s(n-1,0) . s(n-1,1) .... s(n-1,k-2) s(n-1,k-1)
...
row n-k+1: s(k,0).... s(k,1) ...... s(k,k-2) ..s(k,k-1)
row n-k+2: p(n,n-k+1) p(n,n-k+2) .. p(n,n-1) ..p(n,n)
*****
As a class of examples, suppose that (v(n)), for n>=0, is a sequence, that p(0,x)=1, and p(n,x)=v(n)+p(n-1,x) for n>0.  If q(x)=x^2 and s(x)=x+1, and we write the reduction R(p(n,x)) as u1(n)*x+u2(n), then the sequences u1 and u2 are convolutions with the Fibonacci sequence, viz., let F=(0,1,1,2,3,5,8,...)=A000045 and let G=(1,0,1,1,2,3,5,8...); then u1=G**v and u2=F**v, where ** denotes convolution.  Examples (with a few exceptions for initial terms):
...
If v(n)=n! then u1=A192744, u2=A192745.
If v(n)=n+1 then u1=A000071, u2=A001924.
If v(n)=2n then u1=A014739, u2=A027181.
If v(n)=2n+1 then u1=A001911, u2=A001891.
If v(n)=3n+1 then u1=A027961, u2=A023537.
If v(n)=3n+2 then u1=A192746, u2=A192747.
If v(n)=3n then u1=A154691, u2=A192748.
If v(n)=4n+1 then u1=A053311, u2=A192749.
If v(n)=4n+2 then u1=A192750, u2=A192751.
If v(n)=4n+3 then u1=A192752, u2=A192753.
If v(n)=4n then u1=A147728, u2=A023654.
If v(n)=5n+1 then u1=A192754, u2=A192755.
If v(n)=5n then u1=A166863, u2=A192756.
If v(n)=floor((n+1)tau) then u1=A192457, u2=A023611.
If v(n)=floor((n+2)/2) then u1=A052952, u2=A129696.
If v(n)=floor((n+3)/3) then u1=A004695, u2=A178982.
If v(n)=floor((n+4)/4) then u1=A080239, u2=A192758.
If v(n)=floor((n+5)/5) then u1=A124502, u2=A192759.
If v(n)=n+2 then u1=A001594, u2=A192760.
If v(n)=n+3 then u1=A022318, u2=A192761.
If v(n)=n+4 then u1=A022319, u2=A192762.
If v(n)=2^n then u1=A027934, u2=A008766.
If v(n)=3^n then u1=A106517, u2=A094688.

			The first five polynomials and their reductions:
1 -> 1
1+x -> 1+x
2+x+x^2 -> 3+2x
6+2x+x^2+x^3 -> 8+5x
24+6x+2x^2+x^3+x^4 -> 29+13x, so that
A192744=(1,1,3,8,29,...) and A192745=(0,1,2,5,13,...).

Cf. A192232.

A192744p := proc(n,x)
    option remember;
    if n = 0 then
        1;
    else
        x*procname(n-1,x)+n! ;
        expand(%) ;
    end if;
end proc:
A192744 := proc(n)
    local p;
    p := A192744p(n,x) ;
    while degree(p,x) > 1 do
        p := algsubs(x^2=x+1,p) ;
        p := expand(p) ;
    end do:
    coeftayl(p,x=0,0) ;
end proc: # R. J. Mathar, Dec 16 2015

q = x^2; s = x + 1; z = 40;
p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n!;
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}]
  (* A192744 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A192745 *)

G.f.: (1-x)/(1-x-x^2)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 20 2013
Conjecture: a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +3*a(n-3) +(-n+2)*a(n-4)=0. - R. J. Mathar, May 04 2014
Conjecture: (-n+2)*a(n) +(n^2-n-1)*a(n-1) +(-n^2+3*n-3)*a(n-2) -(n-1)^2*a(n-3)
=0. - R. J. Mathar, Dec 16 2015

A014217 a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.

Original entry on oeis.org

1, 1, 2, 4, 6, 11, 17, 29, 46, 76, 122, 199, 321, 521, 842, 1364, 2206, 3571, 5777, 9349, 15126, 24476, 39602, 64079, 103681, 167761, 271442, 439204, 710646, 1149851, 1860497, 3010349, 4870846, 7881196, 12752042, 20633239, 33385281, 54018521, 87403802

Offset: 0

Clark Kimberling

a(n) = floor(lim_{k->oo} Fibonacci(k)/Fibonacci(k-n)). - Jon Perry, Jun 10 2003
For n > 1, a(n) is the maximum element in the continued fraction for A000045(n)*phi. - Benoit Cloitre, Jun 19 2005
a(n) is also the curvature (rounded down) of the circle inscribed in the n-th kite arranged in a spiral, starting with a unit circle, as shown in the illustration in the links section. - Kival Ngaokrajang, Aug 29 2013
a(n) is the n-th Lucas number (A000032) if n is odd, and a(n) is the n-th Lucas number minus 1 if n is even. (Mario Catalani's formula below expresses this fact.) This is related to the fact that the powers of phi approach the values of the Lucas numbers, the odd powers from above and the even powers from below. - Geoffrey Caveney, Apr 18 2014
a(n) is the sum of the last summands over all Arndt compositions of n (see the Checa link). - Daniel Checa, Dec 25 2023
a(n) is the number of (saturated or unsaturated) substituted N-heterocycles in chemistry (N = nitrogen). That means the number of matchings in a cycle graph when the two maximum matchings in every cycle with an even number of vertices are indistinguishable (because the corresponding resonance structures in the molecule are equivalent). - Stefan Schuster, Mar 20 2025

Alois P. Heinz, Table of n, a(n) for n = 0..4784 (first 301 terms from T. D. Noe)
Mohammad K. Azarian, Problem 123, Missouri Journal of Mathematical Sciences, Vol. 10, No. 3, Fall 1998, p. 176. Solution published in Vol. 12, No. 1, Winter 2000, pp. 61-62.
Daniel F. Checa, Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations, 2023. p. 29.
Daniel F. Checa and José L. Ramírez, Arndt Compositions: A Generating Functions Approach, Integers (2024) Vol. 24, A35. See p. 14.
G. Harman, One hundred years of normal numbers
Kival Ngaokrajang, Illustration for n = 0..7
Stefan Schuster and Tatjana Malycheva, Enumeration of saturated and unsaturated substituted N-heterocycles, arXiv:2309.02343 [q-bio.BM], 2023.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Cf. A000032, A000045, A001622, A020956, A022319, A052952, A057146, A062114, A128440, A153382, A169985, A169986, A203976, A226328.

First differences give A181716.

a014217 n = a014217_list !! n
a014217_list = 1 : 1 : zipWith (+)
   a000035_list (zipWith (+) a014217_list $ tail a014217_list)
-- Reinhard Zumkeller, Jan 06 2012

[Floor( ((1+Sqrt(5))/2)^n ): n in [0..100]]; // Vincenzo Librandi, Apr 16 2011

A014217 := proc(n)
    option remember;
    if n <= 3 then
        op(n+1,[1,1,2,4]) ;
    else
        procname(n-1)+2*procname(n-2)-procname(n-3)-procname(n-4) ;
    end if;
end proc: # R. J. Mathar, Jun 23 2013
#
a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-1|2|1>>^n. <<1, 1, 2, 4>>)[1, 1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 12 2017

Table[Floor[GoldenRatio^n], {n, 0, 36}] (* Vladimir Joseph Stephan Orlovsky, Dec 12 2008 *)
LinearRecurrence[{1, 2, -1, -1}, {1, 1, 2, 4}, 40] (* Jean-François Alcover, Nov 05 2017 *)

my(x='x+O('x^44)); Vec((1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2))) \\ Joerg Arndt, Jul 10 2023

from sympy import floor, sqrt
def A014217(n): return floor(((1+sqrt(5))/2)**n) # Chai Wah Wu, Dec 17 2021

[floor(golden_ratio^n) for n in range(37)] # Danny Rorabaugh, Apr 19 2015

a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4).
a(n) = a(n-1) + a(n-2) + (1-(-1)^n)/2 = a(n-1) + a(n-2) + A000035(n).
a(n) = A000032(n) - (1 + (-1)^n)/2. - Mario Catalani (mario.catalani(AT)unito.it), Jan 17 2003
G.f.: (1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2)). - R. J. Mathar, Sep 06 2008
a(2n-1) = (Fibonacci(4n+1)-2)/Fibonacci(2n+2). - Gary Detlefs, Feb 16 2011
a(n) = floor(Fibonacci(2n+3)/Fibonacci(n+3)). - Gary Detlefs, Feb 28 2011
a(2n) = Fibonacci(2*n-1) + Fibonacci(2*n+1) - 1. - Gary Detlefs, Mar 10 2011
a(n+2*k) - a(n) = A203976(k)*A000032(n+k) if k odd, a(n+2*k) - a(n) = A203976(k)*A000045(n+k) if k even, for k > 0. - Paul Curtz, Jun 05 2013
a(n) = A052952(n) - A052952(n-2) + A052952(n-3). - R. J. Mathar, Jun 13 2013
a(n+6) - a(n-6) = 40*A000045(n), case k=6 of my formula above. - Paul Curtz, Jun 13 2013
From Paul Curtz, Jun 17 2013: (Start)
a(n-3) + a(n+3) = A153382(n).
a(n-1) + a(n+2) = A022319(n). (End)
For k > 0, a(2k) = A169985(2k)-1 and a(2k+1) = A169985(2k+1) (which is equivalent to Catalani's 2003 formula). - Danny Rorabaugh, Apr 15 2015
a(n) = ((-1)^(1+n)-1)/2 + ((1-sqrt(5))/2)^n + ((1+sqrt(5))/2)^n. - Colin Barker, Nov 05 2017
a(n) = floor(2*sinh(n*arccsch(2))). - Federico Provvedi, Feb 23 2022
E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2) - cosh(x). - Stefano Spezia, Jul 26 2022
a(n) = floor(Fibonacci(n)*phi) + Fibonacci(n-1) = A074331(n) + A000045(n-1) = A052952(n-1) + A000045(n-1). This is the case k=1 of the formula (also found in A128440): floor(k * phi^n) = floor(Fibonacci(n)*k*phi) + Fibonacci(n-1) * k. - Chunqing Liu, Oct 03 2023

Corrected by T. D. Noe, Nov 09 2006

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar

A192762 Coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

Original entry on oeis.org

0, 1, 6, 13, 26, 47, 82, 139, 232, 383, 628, 1025, 1668, 2709, 4394, 7121, 11534, 18675, 30230, 48927, 79180, 128131, 207336, 335493, 542856, 878377, 1421262, 2299669, 3720962, 6020663, 9741658, 15762355, 25504048, 41266439, 66770524

Offset: 0

Clark Kimberling, Jul 09 2011

The titular polynomial is defined recursively by p(n,x)=x*(n-1,x)+n+4 for n>0, where p(0,x)=1. For discussions of polynomial reduction, see A192232 and A192744.

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

Cf. A192744, A192232, A022319 (first differences).

p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n + 4;
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}]
  (* A022319 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A192762 *)

a(n) = 3*a(n-1)-2*a(n-2)-a(n-3)+a(n-4). G.f.: x*(3*x^2-3*x-1) / ((x-1)^2*(x^2+x-1)). [Colin Barker, Dec 08 2012]

A382379 Length of the long leg in the unique primitive Pythagorean triple (x,y,z) such that (x-y+z)/2 is A000032(n) and such that its long leg and its hypotenuse are consecutive natural numbers.

Original entry on oeis.org

4, 0, 12, 24, 84, 220, 612, 1624, 4324, 11400, 30012, 78804, 206724, 541840, 1419612, 3718264, 9737284, 25496940, 66759012, 174788904, 457622004, 1198100200, 3136716012, 8212108324, 21499706884, 56287170720, 147362061612, 385799428824, 1010036895924

Offset: 0

Miguel-Ángel Pérez García-Ortega, Mar 24 2025

			The triangles begin:
  n=0:      3,     4,     5;
  n=1:      1,     0,     1;
  n=2:      5,    12,    13;
  n=3:      7,    24,    25;
  ...
This sequence gives the middle column

Miguel-Ángel Pérez García-Ortega, El Libro de las Ternas Pitagóricas

Cf. A000032, A022319 (short leg), A382409 (semiperimeter), A382410 (area).

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

A179991 Nonhomogeneous three-term sequence a(n) = a(n-1) + a(n-2) + n.

Original entry on oeis.org

2, 3, 8, 15, 28, 49, 84, 141, 234, 385, 630, 1027, 1670, 2711, 4396, 7123, 11536, 18677, 30232, 48929, 79182, 128133, 207338, 335495, 542858, 878379, 1421264, 2299671, 3720964, 6020665, 9741660, 15762357, 25504050, 41266441, 66770526, 108037003, 174807566

Offset: 1

Carmine Suriano, Aug 05 2010

Extension of Fibonacci sequence, with the addition of natural number equal to the index.

			a(5) = a(4)+a(3)+5 = 8+15+5 = 28.

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000045, A022319 (first differences).

Vec(x*(x-2)*(x^2-x+1) / ((x^2+x-1)*(x-1)^2) + O(x^50)) \\ Colin Barker, Mar 12 2017

a(n) = F(n)+sum(i; i=1 to n)+sum((F(k)*sum(j;j=1 to k-n-1); k=0 to n-4))+2F(n-3).
G.f.: x*(x-2)*(x^2-x+1) / ( (x^2+x-1)*(x-1)^2 ).
Limiting ratio a(n+1)/a(n) is Phi = 1.618034519...
a(n) = 2*A000032(n+1)-n-3. - R. J. Mathar, Aug 09 2010
From Colin Barker, Mar 12 2017: (Start)
a(n) = 2^(-n)*(-3*2^n+(1-sqrt(5))^(1+n) + (1+sqrt(5))^n + sqrt(5)*(1+sqrt(5))^n - 2^n*n).
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>4.
(End)

A258316 T(n,k)=Number of (n+1)X(k+1) 0..1 arrays with each 2X2 subblock having clockwise pattern 0000 or 0011.

Original entry on oeis.org

5, 7, 7, 10, 9, 10, 15, 12, 12, 15, 23, 17, 15, 17, 23, 36, 25, 20, 20, 25, 36, 57, 38, 28, 25, 28, 38, 57, 91, 59, 41, 33, 33, 41, 59, 91, 146, 93, 62, 46, 41, 46, 62, 93, 146, 235, 148, 96, 67, 54, 54, 67, 96, 148, 235, 379, 237, 151, 101, 75, 67, 75, 101, 151, 237, 379, 612

Offset: 1

R. H. Hardin, Jun 29 2015

Table starts
...5...7..10..15..23..36..57..91.146.235.379.612..989.1599.2586.4183.6767.10948
...7...9..12..17..25..38..59..93.148.237.381.614..991.1601.2588.4185.6769.10950
..10..12..15..20..28..41..62..96.151.240.384.617..994.1604.2591.4188.6772.10953
..15..17..20..25..33..46..67.101.156.245.389.622..999.1609.2596.4193.6777.10958
..23..25..28..33..41..54..75.109.164.253.397.630.1007.1617.2604.4201.6785.10966
..36..38..41..46..54..67..88.122.177.266.410.643.1020.1630.2617.4214.6798.10979
..57..59..62..67..75..88.109.143.198.287.431.664.1041.1651.2638.4235.6819.11000
..91..93..96.101.109.122.143.177.232.321.465.698.1075.1685.2672.4269.6853.11034
.146.148.151.156.164.177.198.232.287.376.520.753.1130.1740.2727.4324.6908.11089
.235.237.240.245.253.266.287.321.376.465.609.842.1219.1829.2816.4413.6997.11178
Apparently: put 1s in some number of nonadjacent columns or put 1s in some number of nonadjacent rows

			Some solutions for n=4 k=4
..0..0..0..0..0....1..1..1..1..1....0..0..0..0..0....1..1..1..1..1
..0..0..0..0..0....0..0..0..0..0....0..0..0..0..0....0..0..0..0..0
..0..0..0..0..0....1..1..1..1..1....0..0..0..0..0....0..0..0..0..0
..0..0..0..0..0....0..0..0..0..0....1..1..1..1..1....0..0..0..0..0
..1..1..1..1..1....1..1..1..1..1....0..0..0..0..0....0..0..0..0..0

R. H. Hardin, Table of n, a(n) for n = 1..1104

Column 1 is A018910
Column 2 is A157727(n+3)
Column 3 is A187107(n+3)
Diagonal is A001595(n+2)
Superdiagonal 1 is A000071(n+5)
Superdiagonal 2 is A001610(n+3)
Superdiagonal 3 is A001595(n+4)
Superdiagonal 5 is A022308(n+5)
Superdiagonal 6 is A022319(n+5)
Superdiagonal 7 is A022407(n+5)
Superdiagonal 9 is A022323(n+7)

Empirical: T(n,k) = Fibonacci(n+3) +Fibonacci(k+3) -1

Empirical for rows, columns and nw-se diagonals: a(n) = 2*a(n-1) -a(n-3)

cp's OEIS Frontend

A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A014217 a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A192762 Coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A382379 Length of the long leg in the unique primitive Pythagorean triple (x,y,z) such that (x-y+z)/2 is A000032(n) and such that its long leg and its hypotenuse are consecutive natural numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A179991 Nonhomogeneous three-term sequence a(n) = a(n-1) + a(n-2) + n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A258316 T(n,k)=Number of (n+1)X(k+1) 0..1 arrays with each 2X2 subblock having clockwise pattern 0000 or 0011.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula