A091248 Number of irreducible factors in the factorization of X^n + 1 over GF(2) (counted with multiplicity).

1, 2, 2, 4, 2, 4, 3, 8, 3, 4, 2, 8, 2, 6, 5, 16, 3, 6, 2, 8, 6, 4, 3, 16, 3, 4, 4, 12, 2, 10, 7, 32, 5, 6, 6, 12, 2, 4, 5, 16, 3, 12, 4, 8, 8, 6, 3, 32, 5, 6, 8, 8, 2, 8, 5, 24, 5, 4, 2, 20, 2, 14, 13, 64, 7, 10, 2, 12, 6, 12, 3, 24, 9, 4, 8, 8, 6, 10, 3, 32, 5, 6, 2, 24, 12, 8, 5, 16, 9, 16

Offset: 1

Author

Antti Karttunen, Jan 03 2004

Keywords

• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Antti Karttunen, Scheme-program for computing this sequence.
• Index entries for sequences operating on GF(2)[X]-polynomials.

Crossrefs

Cf. A000374 (number of distinct irreducible factors of the same polynomials).

Cf. A000051, A091222, A318622.

Programs

Maple

h:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2,n/2^padic:-ordp(n,2)) end proc:
f:= n -> add(h(d),d=numtheory:-divisors(n)):
map(f, [$1..100]); # Robert Israel, Aug 30 2018

Mathematica

h[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]];
a[n_] := DivisorSum[n, h];
Array[a, 100] (* Jean-François Alcover, Aug 19 2022, after Robert Israel *)

Formula

a(n) = A091222(A000051(n)).

a(n) = Sum_{d|n} A318622(d). - Robert Israel, Aug 30 2018