The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A318622 Number of irreducible factors in the factorization of the n-th cyclotomic polynomial over GF(2) (counted with multiplicity). 3
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS 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) LINKS 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 FORMULA a(n) = A000010(n)/A002326((A000265(n)-1)/2). A091248(n) = Sum_{d|n} a(d). MAPLE f:= proc(n) option remember; numtheory:-phi(n)/numtheory:-order(2, n/2^padic:-ordp(n, 2)) end proc: map(f, [\$1..200]); MATHEMATICA a[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* Jean-François Alcover, Apr 27 2019 *) PROG (PARI) a(n) = eulerphi(n)/znorder(Mod(2, (n >> valuation(n, 2)))); \\ Michel Marcus, Apr 27 2019 CROSSREFS Cf. A000010, A000265, A002326, A091248, A129832 (a(n)=1). Row 1 of A327818. Sequence in context: A143576 A297159 A293438 * A353785 A245195 A340191 Adjacent sequences: A318619 A318620 A318621 * A318623 A318624 A318625 KEYWORD nonn AUTHOR Robert Israel, Aug 30 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 2 21:27 EDT 2024. Contains 374875 sequences. (Running on oeis4.)