A074033 -id:A074033 - cp's OEIS frontend

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

1, 2, 5, 16, 51, 170, 585, 2048, 7280, 26214, 95325, 349520, 1290555, 4793490, 17895679, 67108864, 252645135, 954437120, 3616814565, 13743895344, 52357696365, 199911205050, 764877654105, 2932031006720, 11258999068416

Offset: 1

N. J. A. Sloane, Apr 18 2000

Also number of Lyndon words of length n with trace 1 over GF(4).
Let x = RootOf( z^2+z+1 ) and y = 1+x. Also number of Lyndon words of length n with trace x over GF(4). Also number of Lyndon words of length n with trace y over GF(4).
Also number of 4-ary Lyndon words (i.e., Lyndon words over Z_4) of length n with trace 1 (mod 4). Also the same with trace 3 (mod 4). - Andrey Zabolotskiy, Dec 19 2020

			a(3; y)=5 since the five Lyndon words over GF(4) of trace y and length 3 are { 00y, 01x, 0x1, 11y, xxy }; the five Lyndon words over Z_4 of trace 1 (mod 4) and length 3 are { 001, 023, 032, 113, 122 }.

Seiichi Manyama, Table of n, a(n) for n = 1..1000
F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
F. Ruskey, Number of q-ary Lyndon words with given trace mod q
F. Ruskey, Number of Lyndon words over GF(q) with given trace

Cf. A000048, A051841, A046211, A046209, A054661, etc.
Cf. A008683, A054661, A027377, A300628, A074033, A074034, A074035, A074448, A074449, A074450.
Cf. A074406, A074407, A074408, A074409.

From Seiichi Manyama, Mar 11 2018: (Start)
a(n) = A000048(2*n) = (1/(4*n)) * Sum_{odd d divides n} mu(d)*4^(n/d), where mu is the Möbius function A008683.
a(n+1) = A300628(n,n) for n >= 0. (End)
From Andrey Zabolotskiy, Dec 19 2020: (Start)
a(n) = A074033(n) + A074034(n) + 2 * A074035(n).
a(n) = A074448(n) + A074449(n) + 2 * A074450(n).
a(n) = A074406(n) + A074407(n) + A074408(n) + A074409(n). (End)

More terms from James Sellers, Apr 19 2000

A074032 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 1.

Original entry on oeis.org

0, 0, 1, 4, 12, 40, 144, 512, 1813, 6528, 23808, 87380, 322560, 1198080, 4473647, 16777216, 63160320, 238605640, 904200192, 3435973836, 13089411609, 49977753600, 191219367936, 733007751680, 2814749599332, 10825959997440, 41699995927744, 160842843834660

Offset: 1

Frank Ruskey and Nate Kube, Aug 26 2002

Let a = RootOf( x^2+x+1 ) and b = 1+a. Same as number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace a. Same as number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace b.

Is this a duplicate of A074450? - R. J. Mathar, Dec 16 2020

E. N. Kuz'min, Irreducible polynomials over a finite field and an analogue of Gauss sums over a field of characteristic 2, Siberian Mathematical Journal, 32, 982-989 (1991).
Jon Maiga, Computer-generated formulas for A074032, Sequence Machine.
Frank Ruskey, Number of irreducible polynomials over GF(4) with given trace and subtrace

Cf. A074031, A074033, A074034, A074035, A042979.

Cf. A074450.

a(n) = A042979(2*n)/2 [discovered by Sequence Machine]. - Andrey Zabolotskiy, Oct 09 2021

More terms from Ruskey's website added by Joerg Arndt, Jan 16 2011

Terms a(17) and beyond from Andrey Zabolotskiy, Dec 15 2020

A074031 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 0.

Original entry on oeis.org

1, 0, 2, 0, 15, 40, 153, 480, 1841, 6528, 23901, 87040, 322875, 1198080, 4474738, 16773120, 63164175, 238605640, 904213989, 3435921408, 13089461538, 49977753600, 191219550297, 733007052640, 2814750270420, 10825959997440, 41699998413248, 160842834247680

Offset: 1

Frank Ruskey and Nate Kube, Aug 26 2002

E. N. Kuz'min, Irreducible polynomials over a finite field and an analogue of Gauss sums over a field of characteristic 2, Siberian Mathematical Journal, 32, 982-989 (1991).
Frank Ruskey, Number of irreducible polynomials over GF(4) with given trace and subtrace

Cf. A074032, A074033, A074034, A074035.

k = 2; q = 2^k;
v[t_] := If[t === 0, q - 1, -1];
dd[a_, n_] := With[{m = Floor[(n + 1)/4]},
   q^(n - 2) + Switch[Mod[n, 4],
     2, 0,
     0, -v[a] q^((n - 2)/2) (-1)^(m k),
     _, v[a] q^((n - 3)/2) (-1)^(m k)
   ]];
h[n_, 0, a_] := 1/n Sum[MoebiusMu[d] (dd[a, n/d] - Boole[EvenQ[n]] q^(n/(2d)-1)), {d, Select[Divisors[n], OddQ]}];
Table[h[n, 0, 0], {n, 30}] (* this sequence *)
Table[h[n, 0, 1], {n, 30}] (* A074032 *)
(* Andrey Zabolotskiy, Dec 15 2020 *)

More terms from Ruskey's website added by Joerg Arndt, Jan 16 2011

Terms a(17) and beyond from Andrey Zabolotskiy, Dec 15 2020

A074034 Number of degree-n irreducible polynomials over GF(4) with trace 1 and subtrace 1.

Original entry on oeis.org

0, 0, 2, 4, 12, 40, 153, 512, 1813, 6528, 23901, 87380, 322560, 1198080, 4474738, 16777216, 63160320, 238605640, 904213989, 3435973836, 13089411609, 49977753600, 191219550297, 733007751680, 2814749599332, 10825959997440, 41699998413248, 160842843834660

Offset: 1

Frank Ruskey and Nate Kube, Aug 26 2002

Let a = RootOf( x^2+x+1 ) and b = 1+a. Same as number of degree-n irreducible polynomials over GF(4) with trace a and subtrace b. Same as number of degree-n irreducible polynomials over GF(4) with trace b and subtrace a.

E. N. Kuz'min, Irreducible polynomials over a finite field and an analogue of Gauss sums over a field of characteristic 2, Siberian Mathematical Journal, 32, 982-989 (1991).
Frank Ruskey, Number of irreducible polynomials over GF(4) with given trace and subtrace

Cf. A074031, A074032, A074033, A074035.

More terms from Ruskey's website added by Joerg Arndt, Jan 16 2011

Terms a(17) and beyond from Andrey Zabolotskiy, Dec 17 2020

A074035 Let a = RootOf( x^2+x+1 ) and b = 1+a. Number of degree-n irreducible polynomials over GF(4) with trace 1 and subtrace a.

Original entry on oeis.org

0, 1, 1, 4, 12, 45, 144, 512, 1813, 6579, 23808, 87380, 322560, 1198665, 4473647, 16777216, 63160320, 238612920, 904200192, 3435973836, 13089411609, 49977848925, 191219367936, 733007751680, 2814749599332, 10825961287995, 41699995927744, 160842843834660

Offset: 1

Frank Ruskey and Nate Kube, Aug 26 2002

Same as number of degree-n irreducible polynomials over GF(4) with trace 1 and subtrace b. Same as number of degree-n irreducible polynomials over GF(4) with trace a and subtrace 1. Same as number of degree-n irreducible polynomials over GF(4) with trace a and subtrace a. Same as number of degree-n irreducible polynomials over GF(4) with trace b and subtrace 1. Same as number of degree-n irreducible polynomials over GF(4) with trace b and subtrace b.

E. N. Kuz'min, Irreducible polynomials over a finite field and an analogue of Gauss sums over a field of characteristic 2, Siberian Mathematical Journal, 32, 982-989 (1991).
Frank Ruskey, Number of irreducible polynomials over GF(4) with given trace and subtrace, The Combinatorial Object Server.

Cf. A074031, A074032, A074033, A074034.

q = 4;
ddpx[n_] := q^(n-2) + q^Quotient[n-2, 2] {-1, 1, -1, 0}[[Mod[n, 4, 1]]];
h1x[n_] :=  1/n Sum[MoebiusMu[d] ddpx[n/d], {d, Select[Divisors[n], OddQ]}];
Table[h1x[n], {n, 30}]
(* Andrey Zabolotskiy, Dec 17 2020 *)

More terms from Ruskey's website added by Joerg Arndt, Jan 16 2011

Terms a(17) and beyond from Andrey Zabolotskiy, Dec 17 2020

cp's OEIS Frontend

A054660 Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A074032 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A074031 Number of degree-n irreducible polynomials over GF(4) with trace 0 and subtrace 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A074034 Number of degree-n irreducible polynomials over GF(4) with trace 1 and subtrace 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A074035 Let a = RootOf( x^2+x+1 ) and b = 1+a. Number of degree-n irreducible polynomials over GF(4) with trace 1 and subtrace a.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions