Primitive Roots of Unity

Question

Let z be a complex number. z is an nth primitive root of unity if for a certain positive integer n and for any positive integer k < n .

Challenge

Write a full program or function that, given a positive integer n as input, outputs all of the nth primitive roots of unity. You may output them in polar form (e^θi or e^iθ, argument should be a decimal with at least 2 decimal places) or rectangular form (a + bi or a similar form, real and imaginary parts should also be decimals), and they may be outputted in your language's list/array format or as a string with the numbers separated by spaces or newlines. Built-ins that calculate the nth roots of unity or the nth primitive roots of unity are not allowed.

This is code-golf, so shortest code in bytes wins.

Sample Inputs and Outputs

6 -> e^1.05i, e^-1.05i # polar form
3 -> e^2.094395i, e^-2.094395i # any number of decimal places is OK as long as there are more than 2
8 -> 0.707 + 0.707i, 0.707 - 0.707i, -0.707 + 0.707i, -0.707 - 0.707i # rectangular form
1 -> 1 + 0i # this is OK
1 -> 1 # this is also OK
4 -> 0 + i, 0 - i # this is OK
4 -> i, -i # this is also OK

Answer 1

Jelly, 11 9 bytes

Thanks to @Dennis for -2 bytes!

Rg=1O÷H-*

I wanted to generate the numbers coprime to N by folding set difference over all of the roots of unity from 1 to N, but I couldn't figure out how so I used @Dennis's method.

Rg=1O÷H-*         Monadic chain:          6
R                 Range                   [1,2,3,4,5,6]
 g                Hook gcds with range    [1,2,3,2,1,6]
  =1              [gcds equal to one]     [1,0,0,0,1,0]
    O             Replicate indices       [1,5]
     ÷H           Divide by half of N     [1/3,5/3]
       -          Numeric literal: - by itself is -1.
        *         Take -1 to those powers [cis π/3,cis 5π/3]

Try it here. Valid in this version of Jelly, but may not be in versions after February 1, 2016.

Answer 2

Jelly, 14 bytes

Rg=1O°÷×ı360Æe

Try it online!

How it works

z = e^2tπi is an n^th root of 1 if and only if t = k / n for some integer k.

z is primitive if and only if k and n are coprime.

Rg=1O°÷×ı360Æe  Main link. Input: n

R               Yield [1, ..., n].
 g              Compute the GCDs of reach integer and n.
  =1            Compare the GCDs with 1.
    O           Get all indices of 1's.
                This computes all the list of all k in [1, ..., n] 
                such that k and n are coprime.
     °          Convert the integers to radians.
      ÷         Divide the results by n.
       ×ı360    Multiply the quotient by the imaginary number 360i.
            Æe  Map exp over the results.

Answer 3

Julia, 48 bytes

n->cis(360deg2rad(filter(k->gcd(k,n)<2,1:n))/n)

This is a lambda function that accepts an integer and returns an array of complex floats. To call it, assign it to a variable. It uses the same approach as Dennis' Jelly answer.

Ungolfed:

function f(n::Int)
    # Get the set of all k < n : gcd(k,n) = 1
    K = filter(k -> gcd(k,n) < 2, 1:n)

    # Convert these to radian measures
    θ = deg2rad(K)

    # Multiply by 360, divide by n
    θ = 360 * θ / n

    # Compute e^iz for all elements z of θ
    return cis(θ)
end

Answer 4

MATL, 27 bytes

:1-tGYf1X-!\Xpg)2j*YP*G/Ze!

Uses release (9.3.1), which is earlier than this challenge.

Try it online!

(The online compiler uses a newer release, but the code runs in release 9.3.1 and gives the same result)

Explanation

There are three main steps:

1. Generate integers 0,1,...,N-1, corresponding to all roots.
2. Keep only integers corresponding to primitive roots. These are identified using the prime factor decomposition of N.
3. Generate the actual roots with an imaginary exponential.

Code:

:1-           % 1. Implicit input "N". Produce vector [0,1,...,N-1]
t             %    duplicate
GYf           % 2. Prime factors of N
1X-           %    remove factor "1" if present (only if N==1)
!\            %    all combinations of [0,1,...,N-1] modulo prime factors of N
Xpg           %    logical "and" along the prime-factor dimension
)             %    index into original vector [0,1,...,N-1] to keep only primitive roots
2j*YP*G/Ze    % 3. Imaginary exponential to produce those roots
!             %    transpose for better output format

Answer 5

Ruby, 46 bytes

This is a non-"golfing language" implementation of Thomas Kwa's Jelly answer.

->n{(1..n).map{|j|1i**(4.0*j/n)if j.gcd(n)<2}}

Ungolfed:

def r(n)
  (1..n).each do |j|
    if j.gcd(n) == 1    # if j is coprime with n, then this will be a primitive root of unity
      p 1i**(4.0*j/n)   # print the fourth power of i**(j/n), i.e. the root of unity
    end
  end
end

Answer 6

Matlab 49 bytes

n=input('');q=0:n-1;exp(i*2*pi/n.*q(gcd(n,q)==1))

Didn't get the task at the first time, but now here it is. Outputs as follows:

6
ans =
    0.5000 + 0.8660i   0.5000 - 0.8660i

Answer 7

ES6, 96 bytes

n=>[...Array(n).keys()].filter(i=>g(i,n)<2,g=(a,b)=>a?g(b%a,a):b).map(i=>'e^'+Math.PI*2*i/n+'i')

Polar form was the shortest output.

Answer 8

PARI/GP, 41 bytes

Pretty straightforward: find the numbers from 1 to n which are coprime to n, then

n->[exp(2*Pi*I*m/n)|m<-[1..n],gcd(n,m)<2]

There has to be some shorter way, but this was the best I could find.