A351915 Number of polynomials of degree n over GF(2) in which the degrees of all distinct irreducible factors are distinct.

1, 2, 3, 6, 12, 24, 47, 94, 186, 372, 732, 1464, 2909, 5818, 11520, 23080, 45890, 91740, 182607, 365214, 727086, 1455764, 2900362, 5799012, 11570477, 23141098, 46148040, 92348504, 184258246, 368453148, 735743974, 1471456940, 2937243564, 5876474992, 11734526504

Offset

0,2

Comments

a(n) is the number of polynomials p in F_2[z] with p = p_1^e_1*...*p_k^e_k where each p_i is irreducible and deg(p_i) != deg(p_j) for all i != j.

Links

Table of n, a(n) for n=0..34.

A. Knopfmacher and R. Warlimont, Distinct degree factorizations for polynomials over a finite field, Trans. Amer. Math. Soc. 347 (1995), no. 6, 2235-2243.

Formula

G.f.: Product_{n>=1} (b(n)/(1-x^n) - b(n) +1) where b(n) = A001037(n).

Example

a(2) = 3 because we have: x^2, (x+1)^2, x^2+x+1.

Mathematica

nn = 30; b := Table[1/n Sum[MoebiusMu[d] 2^(n/d), {d, Divisors[n]}], {n, 1, nn}]; CoefficientList[ Series[Product[b[[i]]/(1 - x^i) - b[[i]] + 1, {i, 1, nn}], {x, 0, nn}], x]

Crossrefs

Cf. A007839, A001037.

Sequence in context: A038085 A124313 A049890 * A262236 A246878 A251709

Adjacent sequences: A351912 A351913 A351914 * A351916 A351917 A351918

Keyword

nonn

Author

Geoffrey Critzer, Feb 25 2022

Status

approved