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

%I #31 Feb 08 2017 12:52:38

%S 1,2,1,4,7,14,28,54,111,218,436,854,1735,3432,6825,13664,27352,54218,

%T 108714,216616,432239,864548,1727408,3441364,6891458,13756440,

%U 27466896,54922134,109751871,219035562,438319568,875529382

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

%H Vincenzo Librandi, <a href="/A007839/b007839.txt">Table of n, a(n) for n = 0..1000</a>

%H A. Knopfmacher and R. Warlimont, <a href="http://dx.doi.org/10.1090/S0002-9947-1995-1277121-X">Distinct degree factorizations for polynomials over a finite field</a>, Trans. Amer. Math. Soc. 347 (1995), no. 6, 2235-2243.

%F G.f.: Product_{m>=1} (1 + pi(m) x^m), where pi(m) = A001037(m) = number of distinct irreducible polynomials of degree m.

%e a(3)=4 from x^3+x+1, x^3+x^2+1, x(x^2+x+1), (x+1)(x^2+x+1).

%t max = 31; pi[n_] := Total[ MoebiusMu[n/#] * (2^#/n)& /@ Divisors[n]]; f[x_] := Product[ 1+pi[n]*x^n, {n, 1, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* _Jean-François Alcover_, Nov 24 2011 *)

%K nonn,easy,nice

%O 0,2

%A _Arnold Knopfmacher_

%E More terms from _David W. Wilson_.