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

0, 1, 0, 3, 4, 6, 20, 28, 64, 136, 240, 528, 1024, 2016, 4160, 8128, 16384, 32896, 65280, 131328, 262144, 523776, 1049600, 2096128, 4194304, 8390656, 16773120, 33558528, 67108864, 134209536, 268451840, 536854528, 1073741824

Offset

0,4

Links

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

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 = 1 if n odd, r = 3 if n even.

a(n) = 2*a(n-2) + 4*a(n-3), n > 3. - Paul Curtz, Feb 06 2008

From Colin Barker, Aug 02 2019: (Start)

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

a(n) = (2^n + i*((-1-i)^n - (-1+i)^n)) / 4 for n>0, where i=sqrt(-1).

(End)

Mathematica

LinearRecurrence[{0, 2, 4}, {0, 1, 0, 3}, 40] (* Harvey P. Dale, Oct 15 2017 *)

Prog

(PARI) concat(0, Vec(x*(1 + x^2) / ((1 - 2*x)*(1 + 2*x + 2*x^2)) + O(x^40))) \\ Colin Barker, Aug 02 2019

Crossrefs

Cf. A038504, A000749, A038518, A038519, A038521.

Sequence in context: A066732 A304679 A265735 * A294990 A081888 A306493

Adjacent sequences: A038517 A038518 A038519 * A038521 A038522 A038523

Keyword

easy,nonn

Author

Frank Ruskey

Status

approved