A091248 - OEIS

%I #23 Aug 20 2022 10:47:56

%S 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,

%T 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,

%U 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

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

%H Robert Israel, <a href="/A091248/b091248.txt">Table of n, a(n) for n = 1..10000</a>

%H Antti Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence</a>.

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>.

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

%F a(n) = Sum_{d|n} A318622(d). - _Robert Israel_, Aug 30 2018

%p h:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2,n/2^padic:-ordp(n,2)) end proc:

%p f:= n -> add(h(d),d=numtheory:-divisors(n)):

%p map(f, [$1..100]); # _Robert Israel_, Aug 30 2018

%t h[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]];

%t a[n_] := DivisorSum[n, h];

%t Array[a, 100] (* _Jean-François Alcover_, Aug 19 2022, after _Robert Israel_ *)

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

%Y Cf. A000051, A091222, A318622.

%K nonn

%O 1,2

%A _Antti Karttunen_, Jan 03 2004