A300675 Number of monic irreducible polynomials of degree n over GF(16) that have a given nonzero trace.

1, 8, 85, 1024, 13107, 174760, 2396745, 33554432, 477218560, 6871947672, 99955602525, 1466015503360, 21651921285435, 321685687669320, 4803839602524143, 72057594037927936, 1085102592571150095, 16397105843297320960, 248545604361560274405, 3777893186295716170752, 57567896172125197996605

Offset: 1

Author

Seiichi Manyama, Mar 11 2018

Keywords

• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..500
• F. Ruskey, C.R. Miers, and J. Sawada, The number of irreducible polynomials and Lyndon words with given trace, SIAM J. Discrete Math. 14 (2001), 240-245.

Crossrefs

Column 16 of A110540.

Cf. A000048, A008683, A054660, A300674.

Programs

Mathematica

a[n_] := DivisorSum[n, MoebiusMu[#] * 16^(n/#) &, OddQ[#] &] / (16*n); Array[a, 21] (* Amiram Eldar, Oct 04 2023 *)

PARI

a(n) = sumdiv(n, d, if (d%2, moebius(d)*16^(n/d)))/(16*n); \\ Michel Marcus, Mar 11 2018

Formula

a(n) = (1/(16*n)) * Sum_{odd d divides n} mu(d)*16^(n/d), where mu is the Möbius function A008683.