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

1, 2, 1, 4, 7, 14, 28, 54, 111, 218, 436, 854, 1735, 3432, 6825, 13664, 27352, 54218, 108714, 216616, 432239, 864548, 1727408, 3441364, 6891458, 13756440, 27466896, 54922134, 109751871, 219035562, 438319568, 875529382

Offset

0,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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_{m>=1} (1 + pi(m) x^m), where pi(m) = A001037(m) = number of distinct irreducible polynomials of degree m.

Example

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

Mathematica

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 *)

Crossrefs

Sequence in context: A357470 A326894 A275778 * A364658 A184345 A045625

Adjacent sequences: A007836 A007837 A007838 * A007840 A007841 A007842

Keyword

nonn,easy,nice

Author

Arnold Knopfmacher

Extensions

More terms from David W. Wilson.

Status

approved