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,2

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.

Formula

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

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

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

Crossrefs

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

Cf. A000051, A091222, A318622.

Sequence in context: A330631 A214560 A152858 * A082991 A214212 A100008

Adjacent sequences: A091245 A091246 A091247 * A091249 A091250 A091251

Keyword

nonn

Author

Antti Karttunen, Jan 03 2004

Status

approved