A013594 -id:A013594 - cp's OEIS frontend

A160340 Indices of records in heights of cyclotomic polynomials (A160338).

1, 105, 385, 1365, 1785, 2805, 3135, 6545, 10465, 11305, 17255, 20615, 26565, 40755, 106743, 171717, 255255, 279565, 327845, 707455, 886445, 983535, 1181895, 1752465, 3949491, 8070699, 10163195, 13441645, 15069565, 30489585, 37495115, 40324935

Offset: 1

Max Alekseyev, May 13 2009

nonn

m is in this sequence if A160338(k) < A160338(m) for all k

Max Alekseyev, Table of n, a(n) for n = 1..42
John Abbott and Nico Mexis, Cyclotomic Factors and LRS-Degeneracy, arXiv:2403.08751 [math.AC], 2024. See p. 12.
Andrew Arnold and Michael Monagan, Calculating cyclotomic polynomials of very large height.
Lola Thompson, Cyclotomic statistics, Univ. Utrecht (Netherlands, 2024). See pp. 6, 14.

Subsequence of A013594 and A046887.

See also A013595, A262404, A262405, A278567.

r = 0; Do[If[# > r, r = #; Print[n]] &@ Max@ Abs@ CoefficientList[Cyclotomic[n, x], x], {n, 10^4}] (* Michael De Vlieger, May 20 2024 *)

print1(r=1); for(n=2,1e4, t=vecmax(abs(Vec(polcyclo(n)))); if(t>r, r=t; print1(", "n))) \\ Charles R Greathouse IV, Jun 28 2012

A063698 Positions of negative coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal. (The constant term in the least significant bit (bit-0), the term x in the next bit (bit-1) and so on).

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 10, 0, 4, 0, 42, 146, 0, 0, 8, 0, 68, 2322, 682, 0, 16, 0, 2730, 0, 1092, 0, 56, 0, 0, 599186, 43690, 8726850, 64, 0, 174762, 9585810, 4112, 0, 792, 0, 279620, 2101256, 2796202, 0, 256, 0, 32800, 2454267026, 4473924, 0, 512

Offset: 0

Antti Karttunen, Aug 03 2001

nonn

Maple procedures Phi_pos_terms and Phi_neg_terms are modeled after the formula given in Lam and Leung paper and they compute correct results for all integers x > 1 and for all n with at most two distinct odd prime factors (that is, up to n=104). Other procedures as in A063696 and A063694.

Antti Karttunen, Table of n, a(n) for n = 0..3003
D. M. Bloom, On the Coefficients of the Cyclotomic Polynomials, Amer.Math.Monthly 75, 372-377, 1968.
T.Y. Lam and K. H. Leung, On the Cyclotomic Polynomial Phi_pq(X), Amer.Math.Monthly 103, 562-564, August-September 1996.
H. Lenstra, Vanishing sums of roots of unity, in Proc. Bicentennial Congress Wiskundig Genootschap (Vrije Univ. Amsterdam, 1978), Part II, pp. 249-268.
Index entries for cyclotomic polynomials, positions of coefficients

A013594, A063696 gives the positions of the positive and A063697 the nonzero terms. This sequence in binary: A063699. A019320[n] = A063696[n]-A063698[n] for up to n=104

with(numtheory); [seq(Phi_neg_terms(j,2),j=0..104)];
Phi_neg_terms := proc(n,x) local a,m,p,q,e,f,r,s; if(n < 2) then RETURN(n); fi; a := op(2, ifactors(n)); m := nops(a); p := a[1][1]; e := a[1][2]; if(1 = m) then RETURN(0); fi; if(2 = m) then q := a[2][1]; f := a[2][2]; r := inv_p_mod_q(p,q)-1; s := inv_p_mod_q(q,p)-1;
RETURN( x^((s+1)*(q^f)*(p^(e-1))) * x^((r+1)*(p^e)*(q^(f-1))) * x^(-((p^e) * (q^f))) * (`if`((p-2)=s,1,(((x^((p-s-1)*((q^f)*(p^(e-1)))))-1)/((x^((q^f)*(p^(e-1))))-1)))) * (`if`((q-2)=r,1,(((x^((q-r-1)*((p^e)*(q^(f-1)))))-1)/((x^((p^e)*(q^(f-1))))-1)))) ); fi;
if((3 = m) and (2 = p)) then if(1 = e) then RETURN(every_other_pos(Phi_neg_terms(n/2,x),x,0)+every_other_pos(Phi_pos_terms(n/2,x),x,1)); else RETURN(dilate(Phi_neg_terms((n/(2^(e-1))),x),x,2^(e-1))); fi; else printf(`Cannot handle argument %a with >=3 distinct odd prime factors!\n`,n); RETURN(0); fi; end;

a[n_] := 2^(Flatten[Position[CoefficientList[Cyclotomic[n, x], x], ?Negative]] - 1) // Total; a[0] = 0; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover, Mar 05 2016 *)

a(n)=my(p); if(n<1, 0, p=polcyclo(n); sum(i=0, n, 2^i*(polcoeff(p, i)<0))) \\ Michel Marcus, Mar 05 2016

A262404 Least k such that the k-th cyclotomic polynomial has n as a coefficient.

Original entry on oeis.org

4, 1, 165, 595, 1785, 1785, 2805, 3135, 6545, 6545, 10465, 10465, 10465, 10465, 10465, 11305, 11305, 11305, 11305, 11305, 11305, 11305, 15015, 11305, 20615, 17255, 20615, 20615, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565

Offset: 0

Charles R Greathouse IV, Sep 21 2015

Suzuki proves that a(n) exists for each n. Vaughan proves that there are infinitely many k with a(n) = k and n > exp(exp(log 2 * log k/log log k)).

			Phi(165) = x^80 + x^79 + x^78 - x^75 - x^74 - x^73 - x^69 - x^68 - x^67 + x^65 + 2x^64 + 2x^63 + x^62 - x^60 - x^59 - x^58 - x^54 - x^53 - x^52 + x^50 + 2x^49 + 2x^48 + 2x^47 + x^46 - x^44 - x^43 - x^42 - x^41 - x^40 - x^39 - x^38 - x^37 - x^36 + x^34 + 2x^33 + 2x^32 + 2x^31 + x^30 - x^28 - x^27 - x^26 - x^22 - x^21 - x^20 + x^18 + 2x^17 + 2x^16 + x^15 - x^13 - x^12 - x^11 - x^7 - x^6 - x^5 + x^2 + x + 1, with 2 as the coefficient of x^16 (among others), and this is the least k for which 2 appears, so a(2) = 165.

Robert Israel, Table of n, a(n) for n = 0..1000
Jiro Suzuki, On coefficients of cyclotomic polynomials, Proc. Japan Acad. Ser. A Math. Sci. 63:7 (1987), pp. 279-280.
R. C. Vaughan, Bounds for the coefficients of cyclotomic polynomials, Michigan Math. J. 21 (1974), 289-295 (1975).

Cf. A013594, A013595, A046887, A262405, A160340, A278567.

N:= 40: count:= 0: A:= Array(0..N): A[0]:= 4:
for k from 1 while count < N do
  S:= select(t -> t::posint and t <= N and A[t] = 0, {coeffs(numtheory:-cyclotomic(k,x),x)}):
  if S <> {} then
    A[convert(S,list)]:= k;
    count:= count + nops(S);
  fi
od:
convert(A,list); # Robert Israel, Dec 23 2018

Table[k = 1; While[! MemberQ[CoefficientList[Cyclotomic[k, x], x], n], k++]; k, {n, 0, 9}] (* Michael De Vlieger, Sep 29 2015 *)

a(n)=my(k,v);while(!setsearch(Set(Vec(polcyclo(k++))),n),);k

Corrected a(22); more terms from Seiichi Manyama, Dec 22 2018

A046887 Numbers n such that the cyclotomic polynomial of order n has a nonzero coefficient which does not appear in any cyclotomic polynomials of lower order.

Original entry on oeis.org

1, 105, 165, 385, 595, 1365, 1785, 2145, 2805, 3135, 6545, 7917, 10465, 11305, 15015, 17255, 20615, 25935, 26565, 40755, 106743, 171717, 255255, 279565, 285285, 327845, 350455, 373065, 463505

Offset: 1

Christoph Lamm (lamm(AT)math.uni-bonn.de)

			The cyclotomic polynomial cycl(105) is the first one to contain a nonzero coefficient which is not 1 or -1: it contains -2. Then for j=165 the coefficient 2 appears, etc.

Cf. A013594.

with(numtheory): me := {}: for j from 1 to 10000 do h := {coeffs(cyclotomic(j,x))}: if me union h <> me then print(j,h minus me); me := me union h; fi; od:

coes = {}; Reap[For[j = 1, j <= 10000, j++, h = Select[ CoefficientList[ Cyclotomic[j, x], x], # != 0 &]; u = Union[coes, h]; If[u != coes, Print[j]; Sow[j]; coes = u]]][[2, 1]] (* Jean-François Alcover, Nov 19 2012, after Maple *)

a(13)-a(19) from Giovanni Resta, Feb 01 2006

Added 10 terms - T. D. Noe, Dec 10 2008

A063696 Positions of positive coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal.

Original entry on oeis.org

0, 2, 3, 7, 5, 31, 5, 127, 17, 73, 21, 2047, 17, 8191, 85, 297, 257, 131071, 65, 524287, 273, 4681, 1365, 8388607, 257, 1082401, 5461, 262657, 4369, 536870911, 387, 2147483647, 65537, 1198665, 87381, 17454241, 4097, 137438953471, 349525

Offset: 0

Antti Karttunen, Aug 03 2001

nonn

D. M. Bloom, On the Coefficients of the Cyclotomic Polynomials, Amer.Math.Monthly 75, 372-377, 1968.
T. Y. Lam and K. H. Leung, On the Cyclotomic Polynomial Phi_pq(X), Amer.Math.Monthly 103, 562-564, August-September 1996.
H. W. Lenstra, Vanishing sums of roots of unity, in Proc. Bicentennial Congress Wiskundig Genootschap (Vrije Univ. Amsterdam, 1978), Part II, pp. 249-268.
Index entries for cyclotomic polynomials, positions of coefficients

Cf. A013594, A063697 (binary version), A063698 (negative terms), A063670 (nonzero terms).

A019320(n) = a(n) - A063698(n) for up to n=104.

with(numtheory); [seq(Phi_pos_terms(j,2),j=0..104)];
inv_p_mod_q := (p,q) -> op(2,op(1,msolve(p*x=1,q))); # Find's p's inverse modulo q.
dilate := proc(nn,x,e) local n,i,s; n := nn; i := 0; s := 0; while(n > 0) do s := s + (((x^e)^i)*(n mod x)); n := floor(n/x); i := i+1; od; RETURN(s); end;
Phi_pos_terms := proc(n,x) local a,m,p,q,e,f,r,s; if(n < 2) then RETURN(x); fi; a := op(2, ifactors(n)); m := nops(a); p := a[1][1]; e := a[1][2]; if(1 = m) then RETURN(((x^(p^e))-1)/((x^(p^(e-1)))-1)); fi; if(2 = m) then q := a[2][1]; f := a[2][2]; r := inv_p_mod_q(p,q)-1; s := inv_p_mod_q(q,p)-1; RETURN( (`if`(0=s,1,(((x^((s+1)*((q^f)*(p^(e-1)))))-1)/((x^((q^f)*(p^(e-1))))-1)))) * (`if`(0=r,1,(((x^((r+1)*((p^e)*(q^(f-1)))))-1)/((x^((p^e)*(q^(f-1))))-1)))) ); fi; if((3 = m) and (2 = p)) then if(1 = e) then RETURN(every_other_pos(Phi_pos_terms(n/2,x),x,0)+every_other_pos(Phi_neg_terms(n/2,x),x,1)); else RETURN(dilate(Phi_pos_terms((n/(2^(e-1))),x),x,2^(e-1))); fi; else printf(`Cannot handle argument %a with three or more distinct odd prime factors!\n`,n); RETURN(0); fi; end;

a[n_] := 2^(Flatten[Position[CoefficientList[Cyclotomic[n, x], x], ?Positive]] - 1) // Total; a[0] = 0; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover, Mar 05 2016 *)

a(n)=local(p); if(n<1,0,p=polcyclo(n); sum(i=0,n,2^i*(polcoeff(p,i)>0)))

A262405 Least k such that the k-th cyclotomic polynomial has -n as a coefficient.

Original entry on oeis.org

4, 1, 105, 385, 1365, 2145, 2805, 3135, 6545, 7917, 10465, 10465, 10465, 10465, 10465, 11305, 11305, 11305, 11305, 11305, 11305, 11305, 15015, 17255, 17255, 17255, 20615, 25935, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565, 26565

Offset: 0

Charles R Greathouse IV, Sep 21 2015

nonn

Suzuki proves that a(n) exists for each n.

			Phi(105) = x^48 + x^47 + x^46 - x^43 - x^42 - 2x^41 - x^40 - x^39 + x^36 + x^35 + x^34 + x^33 + x^32 + x^31 - x^28 - x^26 - x^24 - x^22 - x^20 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 - x^9 - x^8 - 2x^7 - x^6 - x^5 + x^2 + x + 1, with -2 as the coefficient of x^7 (among others), and this is the least k for which -2 appears, so a(2) = 105.

Jiro Suzuki, On coefficients of cyclotomic polynomials, Proc. Japan Acad. Ser. A Math. Sci. 63:7 (1987), pp. 279-280.
R. C. Vaughan, Bounds for the coefficients of cyclotomic polynomials, Michigan Math. J. 21 (1974), 289-295 (1975).

Cf. A013594, A013595, A046887, A262404, A160340, A278567.

Table[k = 1; While[! MemberQ[CoefficientList[Cyclotomic[k, x], x], -n], k++]; k, {n, 0, 9}] (* Michael De Vlieger, Sep 29 2015 *)

a(n)=my(k,v);while(!setsearch(Set(Vec(polcyclo(k++))),-n),);k

More terms from Seiichi Manyama, Dec 22 2018

A063670 Positions of nonzero coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal.

Original entry on oeis.org

2, 3, 3, 7, 5, 31, 7, 127, 17, 73, 31, 2047, 21, 8191, 127, 443, 257, 131071, 73, 524287, 341, 7003, 2047, 8388607, 273, 1082401, 8191, 262657, 5461, 536870911, 443, 2147483647, 65537, 1797851, 131071, 26181091, 4161, 137438953471, 524287

Offset: 0

Antti Karttunen, Aug 03 2001

a(n) = 2^n-1 whenever n is prime. It seems as if a(n) >= A005420(n) for all n (checked up to 200), with equality for all 1A005420(n)=2^n-1 (i.e., 2^n-1 is prime). - M. F. Hasler, Apr 30 2007

a(0) could also be 1. - T. D. Noe, Oct 29 2007

Cf. A013594.
a(n) = A063696(n) (the positive terms) + A063698(n) (the negative terms).
This sequence in binary: A063671.
Cf. A005420.

[seq(Phi_pos_terms(j,2)+Phi_neg_terms(j,2),j=0..104)];

a[n_] := FromDigits[ If[# != 0, 1, 0]& /@ CoefficientList[ Cyclotomic[n, x], x], 2]; a[0] = 2; Table[a[n], {n, 0, 38}] (* Jean-François Alcover, Dec 11 2012 *)

A063670(n)=local(p=polcyclo(n+!n)); if(n,sum(i=0, n, (polcoeff(p, i)<>0)<M. F. Hasler, Apr 30 2007

a(n) = subst(apply(x->x!=0, polcyclo(n,'x)), 'x, 2);  \\ Gheorghe Coserea, Nov 04 2016

A137979 Highest coefficient occurring in the factorization of x^n - 1 over the reals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2

Offset: 1

Ian Miller, Feb 25 2008

nonn

Based on a comment in Mathematica helpfile ref/Factor - Neat Examples.
The first factorization of x^n - 1 in which a 2 appears as a coefficient is for n=105.
Different from A160338, see comment there.

			a(4) = 1 because x^4 - 1 = (x^2+1)(x+1)(x-1) and the highest coefficient of these three terms is 1.
The first time a 2 appears is at n=105, where the factorization is:
(x-1)*(x^6+x^5+x^4+x^3+x^2+x+1)*(x^4+x^3+x^2+x+1)*
(x^24-x^23+x^19-x^18+x^17-x^16+x^14-x^13+x^12-x^11+x^10-x^8+x^7-x^6+x^5-x+1)*
(x^2+x+1)*(x^12-x^11+x^9-x^8+x^6-x^4+x^3-x+1)*
(x^8-x^7+x^5-x^4+x^3-x+1)*
(x^48+x^47+x^46-x^43-x^42-2*x^41-x^40-x^39+x^36+x^35+x^34+x^33+x^32+x^31-x^28-x^26-x^24-x^22-x^20+x^17+x^16+x^15+x^14+x^13+x^12-x^9-x^8-2*x^7-x^6-x^5+x^2+x+1). - _N. J. A. Sloane_, Apr 18 2008

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A013590, A013594.

Table[Max[Abs[Flatten[CoefficientList[Transpose[FactorList[x^i - 1]][[1]], x]]]], {i, 1, 1000}]

a(n) = {my(f = factor(x^n-1)); vecmax(vector(#f~, k, vecmax(apply(x->abs(x), Vec(f[k,1])))));} \\ Michel Marcus, Dec 05 2018

A138474 Maximum possible magnitude of the x^n coefficient of a cyclotomic polynomial.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 5, 4, 4, 4, 5, 5, 6, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 9, 9, 7, 8, 8, 10, 13, 12, 10, 12, 9, 11, 15, 13, 13, 14, 15, 13, 16, 15, 15, 14, 16, 24, 17, 21, 21, 16, 22, 28, 26, 23

Offset: 0

T. D. Noe, Mar 19 2008, Apr 14 2008, Feb 16 2009

nonn

Terms for n <= 30 come from Table 1 of the Gallot et al. paper, which quotes results from Moller. Sequence A138475 gives the minimum order of the cyclotomic polynomial that produces that maximal coefficient. A very fast method (due to Grytczuk and Tropak) for computing the coefficients up to x^k in the cyclotomic polynomial Phi(n,x) is given by the Mathematica function coef[k,n] below.

The first n for which a(n) > n is 118. The sequence appears to be monotonic for n > 143. Terms up to n=128 were found by exhaustive search; subsequent terms were found by a much faster hill-climbing method.

			a(7)=2 is attained for the cyclotomic polynomial Phi(105,x), which has the term -2x^7.

A. Grytczuk and B. Tropak, A numerical method for the determination of the cyclotomic polynomial coefficients, Computational number theory (Debrecen, 1989), 15-19, de Gruyter, Berlin, 1991.

T. D. Noe, Table of n, a(n) for n = 0..1000
John Abbott and Nico Mexis, Cyclotomic Factors and LRS-Degeneracy, arXiv:2403.08751 [math.AC], 2024. See pp. 8-10.
Yves Gallot, Pieter Moree and Huib Hommersom, Value distribution of cyclotomic polynomial coefficients, arXiv:0803.2483 [math.NT], 2008.
H. Möller, Über die i-ten Koeffizienten der Kreisteilungspolynome, Math. Ann. 188 (1970), 26-38.
Carlo Sanna, A Survey on Coefficients of Cyclotomic Polynomials, arXiv:2111.04034 [math.NT], 2021.

Cf. A013594 (smallest order of cyclotomic polynomial containing n or -n as a coefficient).

coef[k_,n_] := Module[{t, b=Table[0,{k+1}]}, t=-MoebiusMu[n]*Table[g=GCD[n,k-m]; MoebiusMu[g]*EulerPhi[g], {m,0,k-1}]; b[[1]]=1; Do[b[[j+1]] = Take[b,j].Take[t,-j]/j, {j,k}]; b]; Table[mx=1; r=PrimePi[k]+1; mnN=Prime[r]; ps=Reverse[Prime[Range[r]]]; Do[d=IntegerDigits[i,2,r]; n=Times@@Pick[ps,d,1]; c=Abs[coef[k,n][[ -1]]]; If[c==mx, mnN=Min[mnN,n], If[c>mx, mx=c; mnN=n]], {i,2^r-1}]; mx, {k,2,20}]

Showing 1-10 of 13 results. Next

cp's OEIS Frontend

A013590 Numbers k such that Phi(k,x) is a cyclotomic polynomial containing a coefficient with an absolute value greater than one.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A160340 Indices of records in heights of cyclotomic polynomials (A160338).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A063698 Positions of negative coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal. (The constant term in the least significant bit (bit-0), the term x in the next bit (bit-1) and so on).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A262404 Least k such that the k-th cyclotomic polynomial has n as a coefficient.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A046887 Numbers n such that the cyclotomic polynomial of order n has a nonzero coefficient which does not appear in any cyclotomic polynomials of lower order.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A063696 Positions of positive coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A262405 Least k such that the k-th cyclotomic polynomial has -n as a coefficient.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions