A091248 -id:A091248 - cp's OEIS frontend

A091222 Number of irreducible polynomials dividing n-th GF(2)[X]-polynomial, counted with multiplicity.

0, 1, 1, 2, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 4, 4, 3, 1, 4, 2, 2, 2, 4, 1, 2, 3, 3, 2, 4, 1, 5, 2, 5, 2, 4, 1, 2, 3, 5, 1, 3, 2, 3, 4, 3, 1, 5, 2, 2, 5, 3, 2, 4, 1, 4, 3, 3, 1, 5, 1, 2, 3, 6, 4, 3, 1, 6, 2, 3, 2, 5, 1, 2, 4, 3, 2, 4, 2, 6, 2, 2, 3, 4, 6, 3, 1, 4, 2, 5, 1, 4, 2, 2, 3, 6, 1, 3, 3, 3, 3, 6

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

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

Cf. A000051, A001222, A091203, A091205, A091248.

Cf. A256170.

for n from 1 to 1000 do
  L:= convert(n,base,2);
  P:= add(L[i]*X^(i-1),i=1..nops(L));
  R:= Factors(P) mod 2;
  a[n]:= add(r[2],r=R[2]);
od:
seq(a[n],n=1..1000); # Robert Israel, Jun 07 2015

a(n)=my(fm=factor(Pol(binary(n))*Mod(1, 2))); sum(k=1, #fm~, fm[k, 2]) \\ Franklin T. Adams-Watters, Jun 07 2015

a(n) = A001222(A091203(n)) = A001222(A091205(n)).

a(A000051(n)) = A091248(n).

A318622 Number of irreducible factors in the factorization of the n-th cyclotomic polynomial over GF(2) (counted with multiplicity).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 1, 2, 2, 8, 2, 1, 1, 2, 2, 1, 2, 4, 1, 1, 1, 4, 1, 2, 6, 16, 2, 2, 2, 2, 1, 1, 2, 4, 2, 2, 3, 2, 2, 2, 2, 8, 2, 1, 4, 2, 1, 1, 2, 8, 2, 1, 1, 4, 1, 6, 6, 32, 4, 2, 1, 4, 2, 2, 2, 4, 8, 1, 2, 2, 2, 2, 2, 8, 1, 2, 1, 4, 8, 3, 2, 4, 8, 2, 6, 4, 6, 2, 2, 16, 2, 2

Offset: 1

Robert Israel, Aug 30 2018

nonn

From Jianing Song, Sep 13 2022: (Start)
a(n) is also the number of irreducible factors in the factorization of the ideal (2) in Z[zeta_n], zeta_n = exp(2*Pi*i/n). Actually, if the n-th cyclotomic polynomial factors as Product_{i=1..a(n)} F_i(x) over GF(2), then the factorization of (2) in Z[zeta_m] is (p) = Product_{i=1..T(n,m)} (2,F_i(zeta_m)). See Page 47-48, Proposition 8.3 and Page 61-62, Proposition 10.3 of the Neukirch link for a proof; see also A327818.
As a result, 2 remains inert in Q(zeta_n) <=> a(n) = 1, which happens if and only if either n is odd, 2 is a primitive root modulo n, or n == 2 (mod 4), 2 is a primitive root modulo n/2.
Example 1: Phi_8(x) = x^4+1 == (x+1)^4 (mod 2), so in Z[zeta_8] = Z[i,sqrt(2)] we have (2) = (2,(zeta_8)+1)^4 = ((zeta_8)+1)^4. In fact we have 2 = -i*(3-2*sqrt(2)) * ((zeta_8)+1)^4.
Example 2: Phi_12(x) = x^4-x^2+1 == (x^2+x+1)^2 (mod 2), so in Z[zeta_12] = Z[i,sqrt(3)] we have (2) = (2,(zeta_12)^2+(zeta_12)+1)^2 = ((zeta_12)^2+(zeta_12)+1)^2. In fact we have 2 = (2-sqrt(3)) * (1-sqrt(-3))/2 * ((zeta_12)^2+(zeta_12)+1)^2. (End)

Robert Israel, Table of n, a(n) for n = 1..10000
Jürgen Neukirch, Algebraic_number_theory
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A000010, A000265, A002326, A091248, A129832 (a(n)=1).

Row 1 of A327818.

f:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2, n/2^padic:-ordp(n, 2)) end proc:
map(f, [$1..200]);

a[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* Jean-François Alcover, Apr 27 2019 *)

a(n) = eulerphi(n)/znorder(Mod(2, (n >> valuation(n, 2)))); \\ Michel Marcus, Apr 27 2019

a(n) = A000010(n)/A002326((A000265(n)-1)/2).

A091248(n) = Sum_{d|n} a(d).

cp's OEIS Frontend

A091222 Number of irreducible polynomials dividing n-th GF(2)[X]-polynomial, counted with multiplicity.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula