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

Author

Max Alekseyev, Nov 18 2009

Keywords

• nonn
• base

Comments

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

Links

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

Crossrefs

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.

Programs

Maple

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

Mathematica

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

PARI

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

PARI

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

Python

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

Formula

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