A265753 -id:A265753 - cp's OEIS frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

1, 0, 2, 1, 6, 7, 22, 36, 89, 168, 377, 756, 1630, 3353, 7110, 14783, 31130, 65016, 136513, 285648, 599041, 1254456, 2629418, 5508097, 11542854, 24183271, 50674318, 106173180, 222470009, 466131960, 976694489, 2046447180, 4287928678, 8984443769, 18825088134

Offset: 1

Clark Kimberling, Jun 26 2011

Polynomial reduction: an introduction
...
We begin with an example.  Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1.  Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1.  Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1.  If p(x)=x^n, then w(x)=x*F(n)+F(n-1), where F=A000045, the sequence of Fibonacci numbers.
In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)s in this manner until reaching w such that d(w)s.
The coefficients of (reduction of p by q->s) comprise a vector of length d(q)-1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n-1)) in the above example.  We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).
Following are examples of reduction by x^2->x+1:
n-th Fibonacci p(x) -> A192232+x*A112576
n-th cyclotomic p(x) -> A192233+x*A051258
n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101
n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236
x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239
(x+1)^n -> A001519+x*A001906
(x^2+x+1)^n -> A154626+x*A087635
(x+2)^n -> A020876+x*A030191
(x+3)^n -> A192240+x*A099453
...
Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n.  We define (reduction of sequence b by q->s) to be the vector given by (reduction of p(n,x) by q->s), with components in the order of powers, from 0 up to d(q)-1.  For k=0,1,...,d(q)-1, we then have the "k-sequence of (reduction of sequence b by q->s)".  Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).
...
For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):
b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
   0-sequence A166536 and 1-sequence A064831.
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
   0-sequence A166516 and 1-sequence A001654.
b=A000027, natural number sequence (1,2,3,4,...) yields
  0-sequence A190062 and 1-sequence A122491.
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
  0-sequence A192243 and 1-sequence A192068.
b=A000217, triangular sequence (1,3,6,10,...) yields
  0-sequence A192244 and 1-sequence A192245.
b=A000290, squares sequence (1,4,9,16,...) yields
  0-sequence A192254 and 1-sequence A192255.
More examples:  A192245-A192257.
...
More comments:
(1) If s(n,x)=(reduction of x^n by q->s) and
    p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then
    (reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)
    +...+p(n-1)s(1,x)+p(n)s(0,x).  See A192744.
(2) For any polynomial p(x), let P(x)=(reduction of p(x)
    by q->s).  Then P(r)=p(r) for each zero r of
    q(x)-s(x).  In particular, if q(x)=x^2 and s(x)=x+1,
    then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
    r=(1-sqrt(5))/2.

			The first four Fibonacci polynomials and their reductions by x^2->x+1 are shown here:
F1(x)=1 -> 1 + 0x
F2(x)=x -> 0 + 1x
F3(x)=x^2+1 -> 2+1x
F4(x)=x^3+2x -> 1+4x
F5(x)=x^4+3x^2+1 -> (x+1)^2+3(x+1)+1 -> 6+6x.
From these, read A192232=(1,0,1,1,6,...) and A112576=(0,1,1,4,6,...).

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

Cf. A168561, A192233 - A192240, A192744.

Cf. A206296, A265398, A265399, A265752, A265753.

q[x_] := x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),  x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[FixedPoint[Expand[#1 /. reductionRules] &, Fibonacci[n, x]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]
  (* A192232 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]
(* A112576 *)
(* Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{1, 3, -1, -1}, {1, 0, 2, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

Vec((1-x-x^2)/(1-x-3*x^2+x^3+x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 08 2013

Empirical G.f.: -x*(x^2+x-1)/(x^4+x^3-3*x^2-x+1). - Colin Barker, Sep 11 2012
The above formula is correct. - Charles R Greathouse IV, Jan 08 2013
a(n) = A265752(A206296(n)). - Antti Karttunen, Dec 15 2015
a(n) = A112576(n) -A112576(n-1) -A112576(n-2). - R. J. Mathar, Dec 16 2015

Example corrected by Clark Kimberling, Dec 18 2017

A104244 Suppose m = Product_{i=1..k} p_i^e_i, where p_i is the i-th prime number and each e_i is a nonnegative integer. Then we can define P_m(x) = Sum_{i=1..k} e_i*x^(i-1). The sequence is the square array A(n,m) = P_m(n) read by descending antidiagonals.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 1, 2, 3, 1, 0, 2, 4, 2, 4, 1, 0, 1, 3, 9, 2, 5, 1, 0, 3, 8, 4, 16, 2, 6, 1, 0, 2, 3, 27, 5, 25, 2, 7, 1, 0, 2, 4, 3, 64, 6, 36, 2, 8, 1, 0, 1, 5, 6, 3, 125, 7, 49, 2, 9, 1, 0, 3, 16, 10, 8, 3, 216, 8, 64, 2, 10, 1, 0, 1, 4, 81, 17, 10, 3, 343, 9, 81, 2, 11, 1, 0, 2, 32, 5

Offset: 1

Olaf Voß, Feb 26 2005

From Antti Karttunen, Jul 29 2015: (Start)
The square array A(row,col) is read by downwards antidiagonals as: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.
A(n,m) (entry at row=n, column=m) gives the evaluation at x=n of the polynomial (with nonnegative integer coefficients) bijectively encoded in the prime factorization of m. See A206284, A206296 for the details of that encoding. (The roles of variables n and m were accidentally swapped in this description, corrected by Antti Karttunen, Oct 30 2016)
(End)
Each row is a completely additive sequence, row n mapping prime(m) to n^(m-1). - Peter Munn, Apr 22 2022

			a(13) = 3 because 3 = p_1^0 * p_2^1 * p_3^0 * ..., so P_3(x) = 0*x^(1-1) + 1*x^(2-1) + 0*x^(3-1) + ... = x. Hence a(13) = A(3,3) = P_3(3) = 3. [Elaborated by _Peter Munn_, Aug 13 2022]
The top left corner of the array:
0, 1,  1, 2,   1,  2,   1,  3,  2,   2,     1,  3,      1,    2,   2, 4
0, 1,  2, 2,   4,  3,   8,  3,  4,   5,    16,  4,     32,    9,   6, 4
0, 1,  3, 2,   9,  4,  27,  3,  6,  10,    81,  5,    243,   28,  12, 4
0, 1,  4, 2,  16,  5,  64,  3,  8,  17,   256,  6,   1024,   65,  20, 4
0, 1,  5, 2,  25,  6,  125, 3, 10,  26,   625,  7,   3125,  126,  30, 4
0, 1,  6, 2,  36,  7,  216, 3, 12,  37,  1296,  8,   7776,  217,  42, 4
0, 1,  7, 2,  49,  8,  343, 3, 14,  50,  2401,  9,  16807,  344,  56, 4
0, 1,  8, 2,  64,  9,  512, 3, 16,  65,  4096, 10,  32768,  513,  72, 4
0, 1,  9, 2,  81, 10,  729, 3, 18,  82,  6561, 11,  59049,  730,  90, 4
0, 1, 10, 2, 100, 11, 1000, 3, 20, 101, 10000, 12, 100000, 1001, 110, 4
...

Cf. A000720.
Transpose: A104245.
Main diagonal: A090883.
Row 1: A001222, row 2: A048675, row 3: A090880, row 4: A090881, row 5: A090882, row 10: A054841; and, in the extrapolated table, row 0: A007814, row -1: A195017.
Other completely additive sequences with prime(k) mapped to a function of k include k: A056239, k-1: A318995, k+1: A318994, k^2: A289506, 2^k-1: A293447, k!: A276075, F(k-1): A265753, F(k-2): A265752.
For completely additive sequences with primes p mapped to a function of p, see A001414.
For completely additive sequences where some primes are mapped to 1, the rest to 0 (notably, some ruler functions) see the cross-references in A249344.
For completely additive sequences, s, with primes p mapped to a function of s(p-1) and maybe s(p+1), see A352957.
See the formula section for the relationship to A073133, A206296.
See the comments for the relevance of A206284.
A297845 represents multiplication of the relevant polynomials.
Cf. A090884, A248663, A265398, A265399 for other related sequences.
A167219 lists columns that contain their own column number.

A(n,A206296(k)) = A073133(n,k). [This formula demonstrates how this array can be used with appropriately encoded polynomials. Note that A073133 reads its antidiagonals by ascending order, while here the order is opposite.] - Antti Karttunen, Oct 30 2016
From Peter Munn, Apr 05 2021: (Start)
The sequence is defined by the following identities:
A(n, 3) = n;
A(n, m*k) = A(n, m) + A(n, k);
A(n, A297845(m, k)) = A(n, m) * A(n, k).
(End)

Starting offset changed from 0 to 1 by Antti Karttunen, Jul 29 2015

Name edited (and aligned with rest of sequence) by Peter Munn, Apr 23 2022

A265752 a(n) = A007814(A265399(n)).

Original entry on oeis.org

0, 1, 0, 2, 1, 1, 1, 3, 0, 2, 2, 2, 3, 2, 1, 4, 5, 1, 8, 3, 1, 3, 13, 3, 2, 4, 0, 3, 21, 2, 34, 5, 2, 6, 2, 2, 55, 9, 3, 4, 89, 2, 144, 4, 1, 14, 233, 4, 2, 3, 5, 5, 377, 1, 3, 4, 8, 22, 610, 3, 987, 35, 1, 6, 4, 3, 1597, 7, 13, 3, 2584, 3, 4181, 56, 2, 10, 3, 4, 6765, 5, 0, 90, 10946, 3, 6, 145, 21, 5, 17711

Offset: 1

Antti Karttunen, Dec 15 2015

nonn

a(n) is the constant term of the reduction by x^2->x+1 of the polynomial encoded in the prime factorization of n. (Assuming here only polynomials with nonnegative integer coefficients, see e.g. A206296 for the details of the encoding).

Completely additive with a(prime(k)) = F(k-2), where F(k) denotes the k-th Fibonacci number, A000045(k) for k >= 0, or A039834(-k) for k <= 0. - Peter Munn, Apr 05 2021, incorporating comment by Antti Karttunen, Dec 15 2015

Antti Karttunen, Table of n, a(n) for n = 1..100

Cf. A007814, A192232, A192750, A206296, A265399, A265750, A265753.

Cf. also A000040, A000045/A039834.

\\ Needs also code from A265398 and A265399.
A265752 = n -> valuation(A265399(n),2);
for(n=1, 100, write("b265752.txt", n, " ", A265752(n)));

(define (A265752 n) (A007814 (A265399 n)))

a(n) = A007814(A265399(n)).
Other identities. For all n >= 1:
a(A000040(n+1)) = A000045(n-1). [Generalized by Peter Munn, Apr 05 2021]
a(A206296(n)) = A192232(n).
a(A265750(n)) = A192750(n).

A265399 Repeatedly perform x^2 -> x+1 reduction for polynomial (with nonnegative integer coefficients) encoded in prime factorization of n, until the polynomial is at most degree 1.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 18, 8, 9, 12, 108, 12, 1944, 36, 18, 16, 209952, 18, 408146688, 24, 54, 216, 85691213438976, 24, 36, 3888, 27, 72, 34974584955819144511488, 36, 2997014624388697307377363936018956288, 32, 324, 419904, 108, 36, 104819342594514896999066634490728502944926883876041385836544, 816293376, 5832, 48

Offset: 1

Antti Karttunen, Dec 15 2015

In terms of integers: apply A265398 as many times as necessary to n, until it gets 3-smooth, one of the terms of A003586.

Completely multiplicative with a(2) = 2, a(3) = 3, a(p) = a(A265398(p)) for p > 3. - Andrew Howroyd & Antti Karttunen, Aug 04 2018

Antti Karttunen, Table of n, a(n) for n = 1..60

Cf. A003586 (fixed points), A065331.

Cf. also A192232, A206296, A265398, A265752, A265753.

f[p_, e_] := If[p < 5, p, a[NextPrime[p, -1] * NextPrime[p, -2]]]^e; a[1] = 1; a[n_] := a[n] = Times @@ f @@@ FactorInteger[n]; Array[a, 40] (* Amiram Eldar, Sep 07 2023 *)

\\ Needs also code from A265398.
A265399(n) = if(A065331(n) == n, n, A265399(A265398(n)));
for(n=1, 60, write("b265399.txt", n, " ", A265399(n)));

(definec (A265399 n) (if (= (A065331 n) n) n (A265399 (A265398 n))))

If A065331(n) = n [that is, when n is one of 3-smooth numbers, A003586] then a(n) = n, otherwise a(n) = a(A265398(n)).
Other identities. For all n >= 1:
a(n) = 2^A265752(n) * 3^A265753(n).

Keyword mult added by Antti Karttunen, Aug 04 2018

A265408 Prime factorization representation of Spironacci polynomials: a(0) = 1, a(1) = 2, and for n > 1, a(n) = A003961(a(n-1)) * a(A265409(n)).

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 38, 138, 870, 9765, 213675, 4309305, 201226025, 9679967297, 810726926009, 40855897091009, 4259653632223561, 380804291082185737, 44319264099050115071, 4644246052673250585913

Offset: 0

Antti Karttunen, Dec 13 2015

nonn

The polynomials encoded by these numbers could also be called "Fernandez spiral polynomials" after Neil Fernandez, who discovered sequence A078510, which is obtained when they are evaluated at X=1.

The polynomial recurrence uses the same composition rules as the Fibonacci polynomials (A206296), but with the neighborhood rules of A078510, where the other polynomial is taken from the nearest inner neighbor (A265409) when the polynomials are arranged as a spiral into a square grid. See A265409 for the illustration.

			n    a(n)   prime factorization    Spironacci polynomial
------------------------------------------------------------
0       1   (empty)                S_0(x) = 0
1       2   p_1                    S_1(x) = 1
2       3   p_2                    S_2(x) = x
3       5   p_3                    S_3(x) = x^2
4       7   p_4                    S_4(x) = x^3
5      11   p_5                    S_5(x) = x^4
6      13   p_6                    S_6(x) = x^5
7      17   p_7                    S_7(x) = x^6
8      38   p_8 * p_1              S_8(x) = x^7 + 1
9     138   p_9 * p_2 * p_1        S_9(x) = x^8 + x + 1

Cf. A003961, A265407, A265409.

Cf. also A078510, A206296 and A265752, A265753.

a(0) = 1, a(1) = 2, and for n >= 2, a(n) = A003961(a(n-1)) * a(A265409(n)).
Other identities. For all n >= 0:
A078510(n) = A001222(a(n)). [when each polynomial is evaluated at x=1]
A265407(n) = A248663(a(n)). [at x=2 over the field GF(2)]

A265750 Prime factorization representation of polynomials defined recursively by p(0,x)=1 and for n>0: p(n,x) = x*p(n-1,x) + 4n+2. (See A192750).

Original entry on oeis.org

2, 192, 3732480, 105815808000000, 15845956399848960000000000, 64521196676588557133336908800000000000000, 11596208520592232147315615803672416545196288000000000000000000, 254410805372253907145905144265082090216385314644252349615132618240000000000000000000000

Offset: 0

Antti Karttunen, Dec 15 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 0..10

Cf. A003961, A192750, A192751, A206296, A265752, A265753.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Using code of Michel Marcus
A265750(n) = if(0==n, 2, A003961(A265750(n-1)) * 2^((4*n)+2));
for(n=0, 10, write("b265750.txt", n, " ", A265750(n)));

(definec (A265750 n) (if (zero? n) 2 (* (A003961 (A265750 (- n 1))) (A000079 (+ 2 (* 4 n))))))

a(0) = 2; for n >= 1, a(n) = A003961(a(n-1)) * 2^((4*n)+2).
Other identities. For all n >= 1:
A192750(n) = A265752(a(n)).
A192751(n) = A265753(a(n)).

A192751 Define a pair of sequences c_n, d_n by c_0=0, d_0=1 and thereafter c_n = c_{n-1}+d_{n-1}, d_n = c_{n-1}+4*n+2; sequence here is c_n.

Original entry on oeis.org

0, 1, 7, 18, 39, 75, 136, 237, 403, 674, 1115, 1831, 2992, 4873, 7919, 12850, 20831, 33747, 54648, 88469, 143195, 231746, 375027, 606863, 981984, 1588945, 2571031, 4160082, 6731223, 10891419, 17622760, 28514301, 46137187, 74651618, 120788939

Offset: 0

Clark Kimberling, Jul 09 2011

nonn

Old definition was: coefficient of x in the reduction under x^2->x+1 of the polynomial p(n,x) defined recursively by p(n,x) = x*p(n-1,x) + 4n+2 for n>0, with p(0,x)=1.

For discussions of polynomial reduction, see A192232 and A192744.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

See A192750 for d_n.

Cf. A000045, A192744, A192232, A022088, A265750, A265752.

(See A192750.)
CoefficientList[Series[x (x^2-4x-1)/((x-1)^2(x^2+x-1)),{x,0,40}],x] (* or *) LinearRecurrence[{3,-2,-1,1},{0,1,7,18},40] (* Harvey P. Dale, Feb 23 2022 *)

G.f.: x*(x^2-4*x-1)/((x-1)^2*(x^2+x-1)). First differences are in A192750. [Colin Barker, Nov 13 2012]
a(n) = 5*Fibonacci(n+3) - (4*n+10). - N. J. A. Sloane, Dec 15 2015
a(n) = A265753(A265750(n)). - Antti Karttunen, Dec 15 2015

Description corrected by Antti Karttunen, Dec 15 2015

Entry revised by N. J. A. Sloane, Dec 15 2015

cp's OEIS Frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A104244 Suppose m = Product_{i=1..k} p_i^e_i, where p_i is the i-th prime number and each e_i is a nonnegative integer. Then we can define P_m(x) = Sum_{i=1..k} e_i*x^(i-1). The sequence is the square array A(n,m) = P_m(n) read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A265752 a(n) = A007814(A265399(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A265399 Repeatedly perform x^2 -> x+1 reduction for polynomial (with nonnegative integer coefficients) encoded in prime factorization of n, until the polynomial is at most degree 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

Extensions

A265408 Prime factorization representation of Spironacci polynomials: a(0) = 1, a(1) = 2, and for n > 1, a(n) = A003961(a(n-1)) * a(A265409(n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A265750 Prime factorization representation of polynomials defined recursively by p(0,x)=1 and for n>0: p(n,x) = x*p(n-1,x) + 4n+2. (See A192750).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A192751 Define a pair of sequences c_n, d_n by c_0=0, d_0=1 and thereafter c_n = c_{n-1}+d_{n-1}, d_n = c_{n-1}+4*n+2; sequence here is c_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions