17
\$\begingroup\$

Background (skip to definitions)

Euler proved a beautiful theorem about the complex numbers: eix = cos(x) + i sin(x).

This makes de Moivre's theorem easy to prove:

(eix)n = ei(nx)

(cos(x) + i sin(x))n = cos(nx) + i sin(nx)

We can plot complex numbers using the two-dimensional Euclidean plane, with the horizontal axis representing the real part and the vertical axis representing the imaginary part. This way, (3,4) would correspond to the complex number 3+4i.

If you are familiar with polar coordinates, (3,4) would be (5,arctan(4/3)) in polar coordinates. The first number, r, is the distance of the point from the origin; the second number, θ, is the angle measured from the positive x-axis to the point, counter-clockwise. As a result, 3 = r cosθ and 4 = r sinθ. Therefore, we can write 3+4i as r cosθ + r i sinθ = r(cosθ + i sinθ) = re.

Let us solve the complex equation zn = 1, where n is a positive integer.

We let z = re. Then, zn = rneinθ. The distance of zn from the origin is rn, and the angle is nθ. However, we know that the distance of 1 from the origin is 1, and the angle is 0. Therefore, rn=1 and nθ=0. However, if you rotate by 2π more, you still end up at the same point, because 2π is just a full circle. Therefore, r=1 and nθ = 2kπ, giving us z=e2ikπ/n.

We restate our discovery: the solutions to zn=1 are z=e2ikπ/n.

A polynomial can be expressed in terms of its roots. For example, the roots of x2-3x+2 are 1 and 2, so x2-3x+2 = (x-1)(x-2). Similarly, from our discovery above:

However, that product certainly contained roots of other n. For example, take n=8. The roots of z4=1 would also be included inside the roots of z8=1, since z4=1 implies z8 = (z4)2 = 12 = 1. Take n=6 as an example. If z2=1, then we would also have z6=1. Likewise, if z3=1, then z6=1.

If we want to extract the roots unique to zn=1, we would need k and n to share no common divisor except 1. Or else, if they share a common divisor d where d>1, then z would be the (k/d)-th root of zn/d=1. Using the technique above to write the polynomial in terms of its roots, we obtain the polynomial:

Note that this polynomial is done by removing the roots of zn/d=1 with d being a divisor of n. We claim that the polynomial above has integer coefficients. Consider the LCM of the polynomials in the form of zn/d-1 where d>1 and d divides n. The roots of the LCM are exactly the roots we wish to remove. Since each component has integer coefficients, the LCM also has integer coefficients. Since the LCM divides zn-1, the quotient must be a polynomial with integer coefficient, and the quotient is the polynomial above.

The roots of zn=1 all have radius 1, so they form a circle. The polynomial represents the points of the circle unique to n, so in a sense the polynomials form a partition of the circle. Therefore, the polynomial above is the n-th cyclotomic polynomial. (cyclo- = circle; tom- = to cut)

Definition 1

The n-th cyclotomic polynomial, denoted , is the unique polynomial with integer coefficients that divide xn-1 but not xk-1 for k<n.

Definition 2

The cyclotomic polynomials are a set of polynomials, one for each positive integer, such that:

where k | n means k divides n.

Definition 3

The n-th cyclotomic polynomial is the polynomial xn-1 divided by the LCM of the polynomials in the form xk-1 where k divides n and k<n.

Examples

  1. Φ1(x) = x - 1
  2. Φ2(x) = x + 1
  3. Φ3(x) = x2 + x + 1
  4. Φ30(x) = x8 + x7 - x5 - x4 - x3 + x + 1
  5. Φ105(x) = x48 + x47 + x46 - x43 - x42 - 2x41 - x40 - x39 + x36 + x35 + x34 + x33 + x32 + x31 - x28 - x26 - x24 - x22 - x20 + x17 + x16 + x15 + x14 + x13 + x12 - x9 - x8 - 2x7 - x6 - x5 + x2 + x + 1

Task

Given a positive integer n, return the n-th cyclotomic polynomial as defined above, in a reasonable format (i.e. e.g. list of coefficients is allowed).

Rules

You may return floating point/complex numbers as long as they round to the correct value.

Scoring

This is . Shortest answer in bytes wins.

References

\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe add 105 as a test? \$\endgroup\$ – Jonathan Allan Sep 27 '17 at 19:47
  • \$\begingroup\$ @JonathanAllan I don't want to type 48 terms \$\endgroup\$ – Leaky Nun Sep 27 '17 at 19:49
  • 1
    \$\begingroup\$ Are floating-point inaccuracies allowed? \$\endgroup\$ – miles Sep 27 '17 at 21:37
  • 3
    \$\begingroup\$ @miles I hate floats with a passion >.< but I'll defend to the death your right to use floats. \$\endgroup\$ – Leaky Nun Sep 27 '17 at 21:39
  • 1
    \$\begingroup\$ May we output complex floating point numbers as long as they yield the correct answer when rounded to the nearest integer/gaussian integer? \$\endgroup\$ – fireflame241 Sep 27 '17 at 23:50

11 Answers 11

12
\$\begingroup\$

Haskell, 120 bytes

import Data.Complex
p%a=zipWith(\x y->x-a*y)(p++[0])$0:p
f n=foldl(%)[1][cis(2*pi/fromInteger n)^^k|k<-[1..n],gcd n k<2]

Try it online!

Gives a list of complex floats that has entries like 1.0000000000000078 :+ 3.314015728506092e-14 due to float inacurracy. A direct method of multiplying out to recover the polynomial from its roots.

The fromInteger is a big concession to Haskell's type system. There's got to be a better way. Suggestions are welcome. Dealing with roots of unity symbolically might also work.


Haskell, 127 bytes

(h:t)%q|all(==0)t=[]|1>0=h:zipWith(\x y->x-h*y)t q%q
f n=foldl(%)(1:(0<$[2..n])++[-1])[tail$f k++[0,0..]|k<-[1..n-1],mod n k<1]

Try it online!

No imports.

Uses the formula

Computes Φ_n(x) by dividing the LHS by each of the other terms in the RHS.

The operator % does division on polynomials, relying on the remainder being zero. The divisor is assumed to be monic, and is given without the leading 1, and also with infinite trailing zeroes to avoid truncating when doing zipWith.

\$\endgroup\$
  • \$\begingroup\$ [0,0..] is a byte shorter than repeat 0. \$\endgroup\$ – Laikoni Sep 27 '17 at 21:40
  • \$\begingroup\$ @flawr Divides polynomials. I think it's the same method as your solution. \$\endgroup\$ – xnor Sep 27 '17 at 21:42
  • \$\begingroup\$ It looks damn elegant, I'm gonna have to get a closer look tomorrow:) \$\endgroup\$ – flawr Sep 27 '17 at 21:45
  • \$\begingroup\$ this answer makes me want to learn Haskell. \$\endgroup\$ – Giuseppe Sep 27 '17 at 22:28
  • 1
    \$\begingroup\$ @xnor -1 byte \$\endgroup\$ – H.PWiz Sep 27 '17 at 23:10
7
\$\begingroup\$

Mathematica, 43 41 bytes

Factor[x^#-1]/Times@@#0/@Most@Divisors@#&

Of course, we can always use the built-in, but if we don't, this divides xn-1 by Φk(x) (computed recursively) for every proper divisor k of n.

We use Factor to get a polynomial at the end. I think the reason this works is that x^#-1 factors into all the cyclotomic polynomials of divisors of n, and then we divide out the ones we don't want.

-2 bytes thanks to Jenny_mathy, rewriting the Factor to only apply to the numerator.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is great! you can save a byte by using Factor@ \$\endgroup\$ – J42161217 Sep 27 '17 at 23:46
  • \$\begingroup\$ @Jenny_mathy Doing that seems to parse as Factor[x^#-1]/Times@@... instead; if we didn't have brackets there, we'd want parentheses. \$\endgroup\$ – Misha Lavrov Sep 28 '17 at 0:04
  • 1
    \$\begingroup\$ ok... but I have to say that when I tested it, it was giving the right results... \$\endgroup\$ – J42161217 Sep 28 '17 at 0:15
  • \$\begingroup\$ That's interesting. It means we can save another byte by writing it Factor[x^#-1]/Times@@..., and it also means I have no clue how it works. \$\endgroup\$ – Misha Lavrov Sep 28 '17 at 0:18
5
\$\begingroup\$

MATL, 32 31 27 25 bytes

Z\"@:@/]XHxvHX~18L*Ze1$Yn

Output may be non-integer due to floating-point inaccuracies (which is allowed). The footer does rounding for clarity.

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Haskell, 250 236 233 218 216 bytes

This is a verbose version, (@xnor can do it in almost half the score) but it is guaranteed to work for any n as long as you have enough memory, but it does not use a builtin for generating the n-th cyclotomic polynomial. The input is an arbitrary size integer and the output is a polynomial type with (exact) rational coefficients.

The rough idea here is calculatin the polynomials recursively. For n=1 or n prime it is trivial. For all other numbers this approach basically uses the formula from definition 2

solved for . Thanks @H.PWiz for quite a bunch of bytes!

import Math.Polynomial
import Data.Ratio
import NumberTheory
p=powPoly x
q=poly LE
c n|n<2=q[-1,1%1]|isPrime n=sumPolys$p<$>[0..n-1]|1>0=fst$quotRemPoly(addPoly(p n)$q[-1])$foldl1 multPoly[c d|d<-[1..n-1],n`mod`d<1]

For n=105 this yields following polynomial (I tidied up all the %1 denominators):

[1,1,1,0,0,-1,-1,-2,-1,-1,0,0,1,1,1,1,1,1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,1,1,1,1,1,1,0,0,-1,-1,-2,-1,-1,0,0,1,1,1]

The polynomial for n=15015 can be found here (the largest coefficient is 23).

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +1 for not being a builtin. \$\endgroup\$ – DJMcMayhem Sep 27 '17 at 20:11
  • \$\begingroup\$ @flawr Why are you using Rationals? It seems to work fine without them \$\endgroup\$ – H.PWiz Sep 27 '17 at 20:42
  • \$\begingroup\$ Does it? I had problems with quotRemPoly, let me try again then! \$\endgroup\$ – flawr Sep 27 '17 at 20:44
  • \$\begingroup\$ Ah the "problem" was that it yields Double coefficients if you don't use Ratio Integer instead, which might cause problems for very (very) large n. \$\endgroup\$ – flawr Sep 27 '17 at 20:46
  • \$\begingroup\$ Eh... I don't think that's a problem. \$\endgroup\$ – H.PWiz Sep 27 '17 at 20:47
3
\$\begingroup\$

Jelly, 23 bytes

R÷
ÆḌÇ€FQœ-@Ç×ı2×ØPÆeÆṛ

Try it online!

Outputs as a list of coefficients.

Has floating point AND complex inaccuracies. Footer does rounding to make output prettier.

\$\endgroup\$
3
\$\begingroup\$

J, 36 bytes

1+//.@(*/)/@(,.~-)_1^2*%*i.#~1=i.+.]

Try it online!

Uses the formula

formula

There are some floating-point inaccuracies, but it is allowed.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 81 bytes

Round@CoefficientList[Times@@(x-E^(2Pi*I#/k)&/@Select[Range[k=#],#~GCD~k<2&]),x]&
\$\endgroup\$
2
\$\begingroup\$

R, 176 171 139 112 bytes

function(n){for(r in exp(2i*pi*(x=1:n)[(g=function(x,y)ifelse(o<-x%%y,g(y,o),y))(x,n)<2]/n))T=c(0,T)-r*c(T,0)
T}

Try it online!

Massively simpler version; uses a for loop rather than a Reduce.

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 8 bytes

A built-in.

polcyclo

Try it online!


Pari/GP, 39 bytes, without built-in

f(n)=p=x^n-1;fordiv(n,d,d<n&&p/=f(d));p

Using the formula:

\$ \Phi_n(x)=\dfrac{x^{n}-1}{\prod\limits_{\stackrel{d|n}{{}_{d<n}}}\Phi_{d}(x)} \$.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

CJam (52 51 bytes)

{M{:K,:!W+K,0-{K\%!},{j($,\:Q,-[{(\1$Qf*.-}*;]}/}j}

Online demo. This is an anonymous block (function) which takes an integer on the stack and leaves a big-endian array of coefficients on the stack.

Dissection

{                    e# Define a block
  M{                 e#   Memoised recursion with no base cases.
    :K,:!W+          e#     Store argument in K and build (x^K - 1)
    K,0-{K\%!},      e#     Find proper divisors of K
    {                e#     Foreach proper divisor D...
      j              e#       Recursive call to get Dth cyclotomic poly
      ($,\:Q,-       e#       The cleverest bit. We know that it is monic, and the
                     e#       poly division is simpler without that leading 1, so
                     e#       pop it off and use it for a stack-based lookup in
                     e#       calculating the number of terms in the quotient.
                     e#       Ungolfed this was (;:Q1$,\,-
                     e#       Store the headless divisor in Q.
      [              e#       Gather terms into an array...
        {            e#         Repeat the calculated number of times...
          (\         e#           Pop leading term, which goes into the quotient.
          1$Qf*.-    e#           Multiply Q by that term and subtract from tail.
        }*;          e#         Discard the array of Q,( zeroes. 
      ]
    }/
  }j
}
\$\endgroup\$
0
\$\begingroup\$

JavaScript(ES6), 337 333 284 ... 252 250 245 242 bytes

(v,z=[e=[1,u=0]],g=(x,y)=>y?g(y,x%y):x,h=Math,m=(l,x,p=h.cos(l),q=h.sin(l),i=0)=>x.map(()=>[(i&&(n=x[i-1])[0])-(w=x[i])[0]*p+w[1]*q,(i++&&n[1])-w[1]*p-w[0]*q]))=>{for(;++u<v;z=g(v,u)-1?z:[...m(h.PI*2*u/v,z),e]);return z.map(r=>h.round(r[0]))}

Explanation (Selected):

z=[e=[1,u=0]]

Initialize z=(1+0i) * x^0

g=(x,y)=>y?g(y,x%y):x

GCD calculation.

h=Math

Since I need to use Math functions quite a lot, I used another variable here.

m=(l,x,p=h.cos(l),q=h.sin(l),i=-1)=>blah blah blah

Polynomial multiplication.

for(;++u<v;z=g(v,u)-1?z:[...m(h.PI*2*u/v,z),e]);

The formula used is

enter image description here

return z.map(r=>h.round(r[0]))

Compress the output back to an integer array.

Outputs:

An array of integers, with the element at position i representing the coefficient of x^i.

One of the problem JS have is that since JS does not provide native library for calculations on polynomials and complex numbers, they needed to be implemented in an array-like way.

console.log(phi(105)) gives

Array(49)
 0:  1    1:  1    2:  1    3: -0    4: -0    5: -1    6: -1 
 7: -2    8: -1    9: -1   10:  0   11: -0   12:  1   13:  1 
14:  1   15:  1   16:  1   17:  1   18:  0   19: -0   20: -1 
21:  0   22: -1   23: -0   24: -1   25:  0   26: -1   27: -0 
28: -1   29:  0   30:  0   31:  1   32:  1   33:  1   34:  1 
35:  1   36:  1   37: -0   38: -0   39: -1   40: -1   41: -2 
42: -1   43: -1   44: -0   45: -0   46:  1   47:  1   48:  1 
length: 49
__proto__: Array(0)

337>333(-4): Changed the code for checking undefined value

333>284(-49): Changed the polynomial multiplication function because it can be simplified

284>277(-7): Deleted some redundant code

277>265(-12): Use 2 variables instead of a 2-element array to drop some bytes in array usage

265>264(-1): Use Array.push() instead of Array.concat() to reduce 4 bytes, but added 3 for the for-loop braces and the z variable

264>263(-1): Further golfed on the last amendment

263>262(-1): Golfed on the for loop

262>260(-2): Golfed out the if clause

260>258(-2): Further combined the declarations

258>252(-6): Golfed on reuse of array references

252>250(-2): Replace some unary operators as binary operators

250>245(-5): Move the increment in Array.map() to the last reference of counter to remove bytes

245>242(-3): Use spread syntax instead of Array.push()

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.