A038521 Number of elements of GF(2^n) with trace 1 and subtrace 1.

0, 2, 1, 4, 10, 12, 36, 64, 120, 272, 496, 1024, 2080, 4032, 8256, 16384, 32640, 65792, 130816, 262144, 524800, 1047552, 2098176, 4194304, 8386560, 16781312, 33550336, 67108864, 134225920, 268419072, 536887296, 1073741824, 2147450880

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

K. Cattel, C. R. Miers, F. Ruskey, J. Sawada, M. Serra, The number of irreducible polynomials over Gf(2) with given trace and subtrace, J. Combin. Math. Combin. Comput. 47 (2003) 31-64. [From R. J. Mathar, Oct 20 2008]

F. Ruskey, Number of irreducible polynomials over GF(2) with given trace and subtrace

F. Ruskey, Number of elements of GF(2^n) with given trace and subtrace

Index entries for linear recurrences with constant coefficients, signature (0,2,4).

Formula

a(n) = C(n, r+0) + C(n, r+4) + C(n, r+8) + ... where r = 3 if n odd, r = 1 if n even.

From Colin Barker, Aug 02 2019: (Start)

G.f.: x*(2 + x) / ((1 - 2*x)*(1 + 2*x + 2*x^2)).

a(n) = ((-1-i)^(-1+n) + (-1+i)^(-1+n) + 2^n) / 2.

a(n) = 2*a(n-2) + 4*a(n-3) for n>2.

(End)

Maple

A038521 := proc(n) local r, a, i ; if n mod 2 = 1 then r := 3 ; else r := 1 ; fi; a :=0 ; for i from r to n by 4 do a := a+binomial(n, i) ; od; a ; end: for n from 1 to 40 do printf("%d, ", A038521(n)) ; od: # R. J. Mathar, Oct 20 2008

Mathematica

LinearRecurrence[{0, 2, 4}, {0, 2, 1}, 33] (* Jean-François Alcover, May 08 2023 *)

Prog

(PARI) concat(0, Vec(x*(2 + x) / ((1 - 2*x)*(1 + 2*x + 2*x^2)) + O(x^35))) \\ Colin Barker, Aug 02 2019
(Magma) I:=[0, 2, 1]; [m le 3 select I[m] else  2*Self(m-2) + 4*Self(m-3): m in [1..33]] // Marius A. Burtea, Aug 02 2019

Crossrefs

Cf. A038504, A000749.

Cf. A038518, A038519, A038520.

Cf. A134654. - R. J. Mathar, Oct 20 2008

Sequence in context: A212770 A205855 A329709 * A134654 A198262 A085421

Adjacent sequences: A038518 A038519 A038520 * A038522 A038523 A038524

Keyword

easy,nonn

Author

Frank Ruskey

Extensions

Values duplicated A038520 and were replaced by R. J. Mathar, Oct 20 2008

Status

approved