A206296 -id:A206296 - cp's OEIS frontend

A168081 Lucas sequence U_n(x,1) over the field GF(2)[x].

0, 1, 2, 5, 8, 21, 34, 81, 128, 337, 546, 1301, 2056, 5381, 8706, 20737, 32768, 86273, 139778, 333061, 526344, 1377557, 2228770, 5308753, 8388736, 22085713, 35782690, 85262357, 134742024, 352649221, 570556418, 1359020033, 2147483648, 5653987329, 9160491010

Offset: 0

Max Alekseyev, Nov 18 2009

The Lucas sequence U_n(x,1) over the field GF(2)={0,1} is: 0, 1, x, x^2+1, x^3, x^4+x^2+1, x^5+x, ... Numerical values are obtained evaluating these 01-polynomials at x=2 over the integers.
The counterpart sequence is V_n(x,1) = x*U_n(x,1) that implies identities like U_{2n}(x,1) = x*U_n(x,1)^2. - Max Alekseyev, Nov 19 2009
Also, Chebyshev polynomials of the second kind evaluated at x=1/2 (A049310) with the resulting coefficients taken modulo 2, and then evaluated at x=2. - Max Alekseyev, Jun 20 2025

G. C. Greubel, Table of n, a(n) for n = 0..1000
Karl-Heinz Hofmann and Frederik P.J. Vandecasteele, Terms in binary, including a visualization.

A bisection of A006921. Cf. A260022. - N. J. A. Sloane, Jul 14 2015
See also A257971, first differences of A006921. - Reinhard Zumkeller, Jul 14 2015
Cf. A000120, A000129, A206296, A248663, A002487.

a:= proc(n) option remember;
      `if`(n<2, n, Bits[Xor](2*a(n-1), a(n-2)))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 16 2025

a[0] = 0; a[1] = 1; a[n_] := a[n] = BitXor[2 a[n - 1], a[n - 2]]; Table[a@ n, {n, 0, 32}] (* Michael De Vlieger, Dec 11 2015 *)

{ a=0; b=1; for(n=1,50, c=bitxor(2*b,a); a=b; b=c; print1(c,", "); ); }

{ a168081(n) = subst(lift(polchebyshev(n-1,2,x/2)*Mod(1,2)),x,2); } \\ Max Alekseyev, Jun 20 2025

def A168081(n): return sum(int(not r & ~(2*n-1-r))*2**(n-1-r) for r in range(n)) # Chai Wah Wu, Jun 20 2022

For n>1, a(n) = (2*a(n-1)) XOR a(n-2).
a(n) = A248663(A206296(n)). - Antti Karttunen, Dec 11 2015
A000120(a(n)) = A002487(n). - Karl-Heinz Hofmann, Jun 16 2025
a(n) = Sum_{k=0..n} (A049310(n,k) mod 2) * 2^k. - Max Alekseyev, Jun 20 2025

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

A265753 a(n) = A007949(A265399(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 15 2015

nonn

a(n) = Coefficient of x in the reduction under 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).

Completely additive with a(prime(k)) = F(k-1), where F(k) denotes the k-th Fibonacci number, A000045(k). - Peter Munn, Mar 29 2021, incorporating comment by Antti Karttunen, Dec 15 2015

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

Cf. A007949, A112576, A192751, A206296, A265399, A265750, A265752.

Cf. also A000040, A000045.

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

(define (A265753 n) (A007949 (A265399 n)))

a(n) = A007949(A265399(n)).
Other identities. For all n >= 1:
a(A000040(n)) = A000045(n-1). [Generalized by Peter Munn, Mar 29 2021]
a(A206296(n)) = A112576(n).
a(A265750(n)) = A192751(n).

A265398 Perform one x^2 -> x+1 reduction for the polynomial with nonnegative integer coefficients that is encoded in the prime factorization of n.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 15, 8, 9, 12, 35, 12, 77, 30, 18, 16, 143, 18, 221, 24, 45, 70, 323, 24, 36, 154, 27, 60, 437, 36, 667, 32, 105, 286, 90, 36, 899, 442, 231, 48, 1147, 90, 1517, 140, 54, 646, 1763, 48, 225, 72, 429, 308, 2021, 54, 210, 120, 663, 874, 2491, 72, 3127, 1334, 135, 64, 462, 210, 3599, 572, 969, 180, 4087, 72

Offset: 1

Antti Karttunen, Dec 15 2015

Completely multiplicative with a(2) = 2, a(3) = 3, a(prime(k)) = prime(k-1) * prime(k-2) for k > 2. - Andrew Howroyd & Antti Karttunen, Aug 04 2018

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

Cf. A064989, A065330, A065331.

Cf. also A192232, A206296, A265399.

a[n_] := a[n] = Module[{k, p, e}, Which[n<4, n, PrimeQ[n], k = PrimePi[n]; Prime[k-1] Prime[k-2], True, Product[{p, e} = pe; a[p]^e, {pe, FactorInteger[n]}]]];
a /@ Range[1, 72] (* Jean-François Alcover, Sep 20 2019 *)
f[p_, e_] := If[p < 5, p, NextPrime[p,-1]*NextPrime[p,-2]]^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Dec 01 2022 *)

A065330(n) = { while(0 == (n%2), n = n/2); while(0 == (n%3), n = n/3); n; }
A065331 = n -> n/A065330(n);
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A265398(n) = { my(a); if(1 == n, n, a = A064989(A065330(n)); A064989(a)*a*A065331(n)); };

r(p) = {my(q = precprime(p-1)); q*precprime(q-1)};
a(n) = {my(f=factor(n)); prod(i=1, #f~, if(f[i,1]<5, f[i,1], r(f[i,1]))^f[i,2])}; \\ Amiram Eldar, Dec 01 2022

(definec (A265398 n) (if (= 1 n) n (* (A065331 n) (A064989 (A065330 n)) (A064989 (A064989 (A065330 n))))))

a(1) = 1; for n > 1, a(n) = A064989(A064989(A065330(n))) * A064989(A065330(n)) * A065331(n).

Sum_{k=1..n} a(k) = c * n^3, where c = (1/3) * Product_{p prime} (p^3-p^2)/(p^3-a(p)) = 0.093529982... . - Amiram Eldar, Dec 01 2022

Keyword mult added by Antti Karttunen, Aug 04 2018

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

A206350 Position of 1/n in the canonical bijection from the positive integers to the positive rational numbers.

Original entry on oeis.org

1, 2, 4, 8, 12, 20, 24, 36, 44, 56, 64, 84, 92, 116, 128, 144, 160, 192, 204, 240, 256, 280, 300, 344, 360, 400, 424, 460, 484, 540, 556, 616, 648, 688, 720, 768, 792, 864, 900, 948, 980, 1060, 1084, 1168, 1208, 1256, 1300, 1392, 1424, 1508, 1548

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

The canonical bijection from the positive integers to the positive rational numbers is given by A038568(n)/A038569(n).
Appears to be a variant of A049696. - R. J. Mathar, Feb 11 2012
Apparently numbers m such that A071912(m) = 1. - Bill McEachen, Aug 01 2023

			The canonical bijection starts with 1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, so that A206297 starts with 1,3,5,9,13 and this sequence starts with 1,2,4,8,12.

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A000010, A008683, A038568, A038569, A049696, A171503, A206296.

Cf. A071912.

[1] cat [2*(&+[EulerPhi(k): k in [1..n-1]]): n in [2..80]]; // G. C. Greubel, Mar 29 2023

1, op(2*ListTools:-PartialSums(map(numtheory:-phi, [$1..100]))); # Robert Israel, Apr 24 2015

a[n_]:= Module[{s=1, k=2, j=1},
  While[s<=n, s= s + 2*EulerPhi[k]; k= k+1];
  s = s - 2*EulerPhi[k-1];
  While[s<=n, If[GCD[j, k-1] == 1,
    s = s+2]; j = j+1];
  If[s>n+1, j-1, k-1]];
t = Table[a[n], {n, 0, 3000}];   (* A038568 *)
ReplacePart[Flatten[Position[t, 1]], 1, 1] (* A206350 *)
(* Second program *)
a[n_]:= If[n==1, 1, 2*Sum[EulerPhi[k], {k, n-1}]];;
Table[a[n], {n, 80}] (* G. C. Greubel, Mar 29 2023 *)

def A206350(n): return 1 if (n==1) else 2*sum(euler_phi(k) for k in range(1,n))
[A206350(n) for n in range(1,80)] # G. C. Greubel, Mar 29 2023

a(1) = 1, a(n+1) = Sum_{k=1..n} mu(k) * floor(n/k) * floor(1 + n/k), where mu(k) is the Moebius function A008683. - Daniel Suteu, May 28 2018

a(n) = 2*Sum_{k=1..n-1} A000010(k), a(1) = 1. - Robert Israel, Apr 24 2015

A277625 Nontrivial values of Fibonacci polynomials.

Original entry on oeis.org

2, 3, 5, 8, 10, 12, 13, 17, 21, 26, 29, 33, 34, 37, 50, 55, 65, 70, 72, 82, 89, 101, 109, 122, 135, 144, 145, 169, 170, 197, 226, 228, 233, 257, 290, 305, 325, 357, 360, 362, 377, 401, 408, 442, 485, 528, 530, 577, 610, 626, 677, 701, 730, 747, 785, 842, 901, 962, 985, 987

Offset: 1

Bobby Jacobs, Oct 24 2016

nonn

The polynomial FibonacciPolynomial(x, y) satisfies the recurrence FibonacciPolynomial(0, y) = 0, FibonacciPolynomial(1, y) = 1, and FibonacciPolynomial(x, y) = y*FibonacciPolynomial(x-1, y) + FibonacciPolynomial(x-2, y).
Nontrivial means a value FibonacciPolynomial(x, y) with x>=3 and y>=1. For FibonacciPolynomial(0, y) = 0 and FibonacciPolynomial(1, y) = 1 for all y, and any number y can be represented trivially as FibonacciPolynomial(2, y).
5 = FibonacciPolynomial(5, 1) = FibonacciPolynomial(3, 2) is the only known number that can be represented as a nontrivial Fibonacci polynomial in more than one way.
Numbers obtained as A104244(n,A206296(k)), where n >= 1 and k >= 3 (all terms from array A073133 except its two leftmost columns) and then sorted into ascending order, with any possible duplicate (5) removed. - Antti Karttunen, Oct 29 2016

			12 is in this sequence because FibonacciPolynomial(4, 2) = 12.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Wikipedia, Fibonacci polynomials.

Cf. A000045, A000129, A001076, A006190, A052918 (FibonacciPolynomial(x, y) for different values of y).
Cf. A002522, A054602, A085151 (FibonacciPolynomial(x, y) for different values of x).
Cf. A073133, A104244, A206296.

Take[Union[Flatten[Table[Fibonacci[x, y], {x, 3, 20}, {y, 50}]]], 60] (* Robert G. Wilson v, Oct 24 2016 *)

list(lim)=my(v=List()); for(y=1,sqrtint(lim\1-1), my(a=y,b=y^2+1); while(b<=lim, listput(v,b); [a,b]=[b,a+y*b])); Set(v) \\ Charles R Greathouse IV, Oct 30 2016

FibonacciPolynomial(x, y) with x>=3 and y>=1.

a(n) = n^2 - 2*n^(5/3) - O(n^(3/2)). - Charles R Greathouse IV, Nov 03 2016

More terms from Robert G. Wilson v, Oct 24 2016

cp's OEIS Frontend

A168081 Lucas sequence U_n(x,1) over the field GF(2)[x].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A265753 a(n) = A007949(A265399(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A265398 Perform one x^2 -> x+1 reduction for the polynomial with nonnegative integer coefficients that is encoded in the prime factorization of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Scheme

Formula

Extensions

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