Akar Persatuan Primitif

11

Membiarkan zmenjadi bilangan kompleks. zadalah akar primitif kesatu jika untuk bilangan bulat positif tertentu n dan untuk bilangan bulat positif k < n .

Tantangan

Tulis sebuah program atau fungsi lengkap yang, diberi bilangan bulat positif nsebagai input, mengeluarkan semua akar keaslian primitif. Anda dapat menampilkannya dalam bentuk kutub ( e^θiatau e^iθ, argumen harus berupa desimal dengan setidaknya 2 tempat desimal) atau bentuk persegi panjang ( a + biatau bentuk yang serupa, bagian nyata dan imajiner juga harus desimal), dan mereka dapat ditampilkan dalam daftar bahasa Anda / Format array atau sebagai string dengan angka yang dipisahkan oleh spasi atau baris baru. Built-in yang menghitung n akar persatuan atau akar n primitif persatuan tidak diperbolehkan.

Ini adalah , jadi kode terpendek dalam byte menang.

Input dan Output Sampel

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
sebuah spaghetto
sumber
Jadi + -i bukan solusi dari z ^ 8 = 1?
RosLuP

Jawaban:

9

Jelly, 11 9 byte

Berkat @Dennis untuk -2 byte!

Rg=1O÷H-*

Saya ingin menghasilkan angka coprime ke N dengan melipat set perbedaan pada semua akar persatuan dari 1 ke N, tetapi saya tidak tahu bagaimana saya menggunakan metode @ Dennis.

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]

Coba di sini . Berlaku dalam versi Jelly ini, tetapi mungkin tidak dalam versi setelah 1 Februari 2016.

lirtosiast
sumber
4

Jelly , 14 byte

Rg=1O°÷×ı360Æe

Cobalah online!

Bagaimana itu bekerja

z = e 2tπi adalah n th akar 1 jika dan hanya jika t = k / n untuk beberapa bilangan bulat k .

z adalah primitif jika dan hanya jika k dan n adalah koprime.

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.
Dennis
sumber
2

Julia, 48 byte

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

Ini adalah fungsi lambda yang menerima integer dan mengembalikan array float kompleks. Untuk menyebutnya, tetapkan ke variabel. Ini menggunakan pendekatan yang sama dengan jawaban Dennis 'Jelly.

Tidak Disatukan:

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
Alex A.
sumber
2

Ruby, 46 byte

Ini adalah implementasi non-"golfing language" dari jawaban Jelly Thomas Kwa .

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

Tidak Disatukan:

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
Sherlock9
sumber
2

MATL , 27 byte

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

Menggunakan rilis (9.3.1) , yang lebih awal dari tantangan ini.

Cobalah online!

(Kompilator online menggunakan rilis yang lebih baru, tetapi kode berjalan di rilis 9.3.1 dan memberikan hasil yang sama)

Penjelasan

Ada tiga langkah utama:

  1. Hasilkan bilangan bulat 0,, 1... N-1,, sesuai dengan semua root.
  2. Simpan hanya bilangan bulat yang sesuai dengan akar primitif. Ini diidentifikasi menggunakan dekomposisi faktor utama N.
  3. Hasilkan akar yang sebenarnya dengan eksponensial imajiner.

Kode:

: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
Luis Mendo
sumber
1

Matlab 49 byte

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

Tidak mendapatkan tugas pada saat pertama, tetapi sekarang ini dia. Output sebagai berikut:

6
ans =
    0.5000 + 0.8660i   0.5000 - 0.8660i
brainkz
sumber
3
Jawaban Anda menampilkan semua akar persatuan, bukan hanya yang primitif .
flawr
@ flawr terima kasih atas komentarnya, saya tidak mendapatkan tugas pada awalnya. Saya mengedit solusi
brainkz
1

ES6, 96 byte

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')

Bentuk kutub adalah keluaran terpendek.

Neil
sumber
1

PARI / GP, 41 byte

Cukup mudah: cari angka dari 1 hingga n yang merupakan koprime ke n, lalu

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

Pasti ada cara yang lebih singkat, tetapi ini adalah yang terbaik yang bisa saya temukan.

Charles
sumber