A160340 -id:A160340 - cp's OEIS frontend

A013595 Irregular triangle read by rows: coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order).

0, 1, -1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 0, 1, -1, 1, 0, -1, 1

Offset: 0

N. J. A. Sloane

We follow Maple in defining Phi_0 to be x; it could equally well be taken to be 1.
From Wolfdieter Lang, Oct 29 2013: (Start)
The length of row n  >= 1 of this  table is phi(n) + 1 = A000010(n) + 1. Row n = 0 has here length 2.
Phi_n(x) is the minimal polynomial of omega_n := exp(i*2*Pi/n) over the rationals. Namely, Phi_n(x) = Product_{k=0..n-1, gcd(k,n)=1} (x - (omega_n)^k). See the Graham et al. reference, 4.50 a, pp. 149, 506.
Phi_n(x) = Product_{d|n} (x^d - 1)^(mu(n/d)) with the Moebius function mu(n) = A008683(n), n >= 1. See the Graham et al. reference, 4.50 b, pp. 149, 506.
Phi_n(x) = Phi_{rad(n)}(x^(n/rad(n))), n >= 2, with rad(n) = A007947(n), the squarefree kernel of n. Proof from the preceding formula, where only squarefree n/d (A005117) from the set of divisors of n enter, by mapping each factor (numerator or denominator) of the left hand side to one of the right hand side and vice versa.
(End)
Each row can be considered as the last column of the companion matrix of the cyclotomic polynomial: A000010(n) is the size of such a square matrix, last column has opposite signs and the last term (before last term of each row in A013595) equal to A008683(n). - Eric Desbiaux, Dec 14 2015

			Phi_0 = x; Phi_1 = x - 1; Phi_2 = x + 1; Phi_3 = x^2 + x + 1; Phi_4 = x^2 + 1; ...
From _Wolfdieter Lang_, Oct 29 2013: (Start)
The irregular triangle a(n,m) begins:
n\m 0  1  2  3  4  5  6  7  8  9 10 11 12 ...
0:  0  1
1: -1  1
2:  1  1
3:  1  1  1
4:  1  0  1
5:  1  1  1  1  1
6:  1 -1  1
7:  1  1  1  1  1  1  1
8:  1  0  0  0  1
9:  1  0  0  1  0  0  1
10: 1 -1  1 -1  1
11: 1  1  1  1  1  1  1  1  1  1  1
12: 1  0 -1  0  1
13: 1  1  1  1  1  1  1  1  1  1  1  1  1
14: 1 -1  1 -1  1 -1  1
15: 1 -1  0  1 -1  1  0 -1  1
...
Phi_15(x) = (x^1 - 1)*((x^3 - 1)^(-1))*((x^5 - 1)^(-1))*(x^15 - 1) because mu(15) = mu(1) = +1 and mu(3) = mu(5) = -1. Hence Phi_15(x) = 1 - x + x^3 - x^4 + x^5 - x^7 + x^8, giving row n = 15.
Example for the reduction via the squarefree kernel: Phi_12(x) = Phi_6(x^(12/6)) = Phi_6(x^2). By the formula with the Mobius function Phi_6(x) = Phi_2(x^3)/Phi_2(x) = 1 - x + x^2 and with x -> x^2 this becomes Phi_12(x) = 1 - x^2 + x^4.
(End)

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968; see p. 90.
Z. I. Borevich and I. R. Shafarevich, Number Theory. Academic Press, NY, 1966, p. 325.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1991, p. 137.
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194.

Robert Israel, Table of n, a(n) for n = 0..10000
Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bull. Amer. Math. Soc. 42 (1936), 389-392.
Rakshith Rajashekar, Marco Di Renzo, K.V.S. Hari, L. Hanzo, A generalised transmit and receive diversity condition for feedback assisted MIMO systems: theory & applications in full-duplex spatial modulation, 2017.
Eric Weisstein's World of Mathematics, Cyclotomic Polynomial.
Wikipedia, Cyclotomic Polynomial.

Cf. A013596, A020500 (row sums, n >= 1), A020513 (alternating row sums).
For record coefficients see A160340, A262404, A262405, A278567.
Column m=1 is A157657.

N:= 100:  # to get coefficients up to cyclotomic(N,x)
with(numtheory):
for n from 0 to N do
  C:= cyclotomic(n,x);
  L[n]:= seq(coeff(C,x,i),i=0..degree(C));
od:
A:= [seq](L[n],n=0..N): # note that A013595(n) = A[n+1]
# Robert Israel, Apr 17 2014

Table[CoefficientList[x^KroneckerDelta[n] Cyclotomic[n, x], x], {n, 0, 15}] // Flatten (* Peter Luschny, Dec 27 2016 *)

row(n) = if (n==0, p=x, p = polcyclo(n)); Vecrev(p); \\ Michel Marcus, Dec 14 2015

a(n,m) = [x^m] Phi_n(x), n >= 0, 0 <= m <= phi(n), with phi(n) = A000010(n). - Wolfdieter Lang, Oct 29 2013

Maple program corrected by Robert Israel, Apr 17 2014

A013596 Irregular triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in decreasing order).

Original entry on oeis.org

1, 0, 1, -1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 0, 1, -1, 1, 0, -1, 1, 1, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

We follow Maple in defining Phi_0 to be x; it could equally well be taken to be 1.

			Phi_0 = x             --> Row 0: [1, 0]
Phi_1 = x - 1         --> Row 1: [1, -1]
Phi_2 = x + 1         --> Row 2: [1, 1]
Phi_3 = x^2 + x + 1   --> Row 3: [1, 1, 1]
Phi_4 = x^2 + 1       --> Row 4: [1, 0, 1]
etc. After row zero, each row n has A039649(n) terms.

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968; see p. 90.
Z. I. Borevich and I. R. Shafarevich, Number Theory. Academic Press, NY, 1966, p. 325.
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194.

Antti Karttunen, Table of n, a(n) for n = 0..45566, rows 0..385 flattened

Version with reversed rows: A013595.

Cf. A039649, A160340.

with(numtheory): [ seq(cyclotomic(n,x), n=0..48) ];

Join[{1, 0}, Table[ CoefficientList[ Cyclotomic[n, x], x] // Reverse, {n, 1, 16}] // Flatten] (* Jean-François Alcover, Dec 11 2012 *)

A013595row(n) = { if(!n, p=x, p = polcyclo(n)); Vecrev(p); }; \\ This function from Michel Marcus's code for A013595.
n=0; for(r=0,385,v=A013595row(r);k=length(v);while(k>0,write("b013596.txt", n, " ", v[k]);n=n+1;k=k-1)); \\ Antti Karttunen, Aug 13 2017

Example section edited by Antti Karttunen, Aug 13 2017

A278567 Maximal coefficient (in absolute value) of cyclotomic polynomial C(N,x), where N = n-th number which is a product of exactly three distinct primes = A007304(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2

Offset: 1

N. J. A. Sloane, Nov 26 2016

nonn

E. Lehmer (1936) shows that this sequence is unbounded.

			The first 2 occurs in the famous C(105,x), which is 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.

Alois P. Heinz, Table of n, a(n) for n = 1..20000
Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bull. Amer. Math. Soc. 42 (1936), 389-392.

See A278571 for smallest m such that a(m) = n.
Cf. A007304, A013595, A160340, A262404, A262405.
See A278570 for another version.

with(numtheory):
b:= proc(n) option remember; local k;
      for k from 1+`if`(n=1, 0, b(n-1)) while
      bigomega(k)<>3 or nops(factorset(k))<>3 do od; k
    end:
a:= n-> max(map(abs, [coeffs(cyclotomic(b(n), x))])):
seq(a(n), n=1..120);  # Alois P. Heinz, Nov 26 2016

f[n_] := Max[ Abs[ CoefficientList[ Cyclotomic[n, x], x]]]; t = Take[ Sort@ Flatten@ Table[Prime@i Prime@j Prime@k, {i, 3, 35}, {j, 2, i -1}, {k, j -1}], 105]; f@# & /@ t (* Robert G. Wilson v, Dec 09 2016 *)

from math import isqrt
from sympy import primepi, primerange, integer_nthroot, cyclotomic_poly
def A278567(n):
    def f(x): return int(n+x-sum(primepi(x//(k*m))-b for a,k in enumerate(primerange(integer_nthroot(x,3)[0]+1),1) for b,m in enumerate(primerange(k+1,isqrt(x//k)+1),a+1)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return max(int(abs(x[1][0][0])) for x in cyclotomic_poly(bisection(f)).as_terms()[0]) # Chai Wah Wu, Aug 31 2024

A160338 Height (maximum absolute value of coefficients) of the n-th cyclotomic polynomial.

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

Max Alekseyev, May 13 2009

Different from A137979: first time these sequence disagree is at n=14235 with a(14235)=2 and A137979(14235)=3.

			a(4) = 1 because the 4th cyclotomic polynomial x^2 + 1 has height 1.

Max Alekseyev, Table of n, a(n) for n = 1..100000
Alexandre Kosyak, Pieter Moree, Efthymios Sofos and Bin Zhang, Cyclotomic polynomials with prescribed height and prime number theory, arXiv:1910.01039 [math.NT], 2019.
Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bull. Amer. Math. Soc. 42 (1936), 389-392.
H. Maier, The coefficients of cyclotomic polynomials, Analytic number theory, Vol. 2 (1995), pp. 633-639, Progr. Math., 139.
Lola Thompson, Heights of divisors of x^n-1, arXiv:1111.5404 [math.NT], 2011.
R. C. Vaughan, Bounds for the coefficients of cyclotomic polynomials, Michigan Math. J. 21 (1974), 289-295 (1975).

Cf. A160339 (records), A160340 (indices of records), A160341.

Table[Max@Abs@CoefficientList[Cyclotomic[n,x],x],{n,1,105}] (* from Jean-François Alcover, Apr 02 2011 *)

PARI
```
a(n) = vecmax(abs(Vec(polcyclo(n))))
```

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

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

A160339 Records in heights of cyclotomic polynomials (A160338).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 14, 23, 25, 27, 59, 359, 397, 434, 532, 1182, 31010, 35111, 44125, 59815, 14102773, 14703509, 56938657, 74989473, 1376877780831, 1475674234751, 1666495909761, 2201904353336, 2286541988726, 2699208408726, 862550638890874931

Offset: 1

Max Alekseyev, May 13 2009

nonn

Max Alekseyev, Table of n, a(n) for n = 1..42
A. Arnold and M. Monagan, Calculating cyclotomic polynomials of very large height.

Cf. A160338, A160340.

a(n) = A160338(A160340(n)).

A189408 Least k where Phi(k) has height greater than k^n, where Phi(k) is the k-th cyclotomic polynomial and the height is the largest absolute value of the coefficients.

Original entry on oeis.org

1181895, 43730115, 416690995, 1880394945

Offset: 1

Charles R Greathouse IV, Apr 21 2011

Arnold & Monagan compute this sequence to demonstrate their fast algorithm for computing cyclotomic polynomials.

This sequence is infinite because (the supremum of) A160338 grows exponentially.

Andrew Arnold and Michael Monagan, A high-performance algorithm for calculating cyclotomic polynomials, PASCO 2010. doi:10.1145/1837210.1837228
Andrew Arnold and Michael Monagan, A fast recursive algorithm for computing cyclotomic polynomials, ACM Commun. Comput. Algebra 44:3/4 (2010), pp. 89-90. doi:10.1145/1940475.1940479
Andrew Arnold and Michael Monagan, Calculating cyclotomic polynomials, Mathematics of Computation 80 (276) (2011) 2359-2379 preprint.
Andrew Arnold and Michael Monagan, Cyclotomic Polynomials

Subsequence of A160340. Cf. A160338, A108975.

cp's OEIS Frontend

A013595 Irregular triangle read by rows: coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A013596 Irregular triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in decreasing order).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A278567 Maximal coefficient (in absolute value) of cyclotomic polynomial C(N,x), where N = n-th number which is a product of exactly three distinct primes = A007304(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A160338 Height (maximum absolute value of coefficients) of the n-th cyclotomic polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

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

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

A160339 Records in heights of cyclotomic polynomials (A160338).

Views