Latar Belakang (lewati ke definisi)

Euler membuktikan teorema yang indah tentang bilangan kompleks: e ^ix = cos (x) + i sin (x).

Ini membuat teorema de Moivre mudah dibuktikan:

(e ^ix ) ⁿ = e ^{i (nx)}

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

Kita dapat memplot bilangan kompleks menggunakan bidang Euclidean dua dimensi, dengan sumbu horizontal mewakili bagian nyata dan sumbu vertikal mewakili bagian imajiner. Dengan cara ini, (3,4) akan sesuai dengan bilangan kompleks 3 + 4i.

Jika Anda terbiasa dengan koordinat polar, (3,4) akan menjadi (5, arctan (4/3)) dalam koordinat polar. Angka pertama, r, adalah jarak titik dari titik asal; angka kedua, θ, adalah sudut yang diukur dari sumbu x positif ke titik, berlawanan arah jarum jam. Akibatnya, 3 = r cosθ dan 4 = r sinθ. Oleh karena itu, kita dapat menulis 3 + 4i sebagai r cosθ + ri sinθ = r (cosθ + i sinθ) = re ^iθ .

Mari kita memecahkan persamaan kompleks z ⁿ = 1, di mana n adalah bilangan bulat positif.

Kami membiarkan z = re ^iθ . Kemudian, z ⁿ = r ⁿ e ^inθ . Jarak z ⁿ dari titik asal adalah r ⁿ , dan sudutnya adalah nθ. Namun, kita tahu bahwa jarak 1 dari titik asal adalah 1, dan sudutnya adalah 0. Oleh karena itu, r ⁿ = 1 dan nθ = 0. Namun, jika Anda memutar 2π lebih, Anda masih berakhir pada titik yang sama, karena 2π hanya lingkaran penuh. Oleh karena itu, r = 1 dan nθ = 2kπ, memberi kita z = e ^{2ikπ / n} .

Kami menyatakan kembali penemuan kami: solusi untuk z ⁿ = 1 adalah z = e ^{2ikπ / n} .

Polinomial dapat diekspresikan dalam hal akarnya. Misalnya, akar x ² -3x + 2 adalah 1 dan 2, jadi x ² -3x + 2 = (x-1) (x-2). Demikian pula dari penemuan kami di atas:

Namun, produk itu tentu mengandung akar n lain. Misalnya, ambil n = 8. Akar z ⁴ = 1 juga akan dimasukkan ke dalam akar z ⁸ = 1, karena z ⁴ = 1 menyiratkan z ⁸ = (z ⁴ ) ² = 1 ² = 1. Ambil n = 6 sebagai contoh. Jika z ² = 1, maka kita juga akan memiliki z ⁶ = 1. Demikian juga, jika z ³ = 1, maka z ⁶ = 1.

Jika kita ingin mengekstrak akar unik ke z ⁿ = 1, kita perlu k dan n untuk tidak berbagi pembagi umum kecuali 1. Atau, jika mereka berbagi pembagi umum d di mana d> 1, maka z akan menjadi (k / d) -th root dari z ^{n / d} = 1. Dengan menggunakan teknik di atas untuk menulis polinom dalam hal akarnya, kita memperoleh polinomial:

Perhatikan bahwa polinomial ini dilakukan dengan menghilangkan akar z ^{n / d} = 1 dengan d menjadi pembagi n. Kami mengklaim bahwa polinomial di atas memiliki koefisien bilangan bulat. Pertimbangkan LCM polinomial dalam bentuk z ^{n / d} -1 di mana d> 1 dan d membagi n. Akar LCM adalah persis akar yang ingin kita hapus. Karena setiap komponen memiliki koefisien integer, LCM juga memiliki koefisien integer. Karena LCM membagi z ⁿ -1, hasil bagi harus polinomial dengan koefisien integer, dan hasil bagi adalah polinomial di atas.

Akar z ⁿ = 1 semuanya memiliki jari-jari 1, sehingga mereka membentuk lingkaran. Polinomial mewakili titik-titik lingkaran yang unik ke n, jadi dalam arti polinomial membentuk partisi dari lingkaran. Oleh karena itu, polinomial di atas adalah polinomial siklomomik ke-n. (cyclo- = lingkaran; tom- = untuk memotong)

Definisi 1

Polinomial siklotomik ke-n, dilambangkan , adalah polinomial unik dengan koefisien bilangan bulat yang membagi x ⁿ -1 tetapi bukan x ^k -1 untuk k <n.

Definisi 2

Polinomial siklomomik adalah sekumpulan polinomial, satu untuk setiap bilangan bulat positif, sehingga:

dimana k | n berarti k membagi n.

Definisi 3

Polinomial siklomomik ke-n adalah polinomial ^xn -1 dibagi dengan LCM polinomial dalam bentuk ^xk -1 di mana k membagi n dan k <n.

Contohnya

1. Φ ₁ (x) = x - 1
2. Φ ₂ (x) = x + 1
3. Φ ₃ (x) = x ² + x + 1
4. Φ ₃₀ (x) = x ⁸ + x ⁷ - x ⁵ - x ⁴ - x ³ + x + 1
5. Φ ₁₀₅ (x) = x ⁴⁸ + x ⁴⁷ + x ⁴⁶ - x ⁴³ - x ⁴² - 2x ⁴¹ - x ⁴⁰ - x ³⁹ + x ³⁶ + x ³⁵ + x ³⁴ + x ³³ + x ³³ + x ³² + x ³¹ - x ²⁸ - x ²⁶ - x ²⁴ - x ²² - x ²⁰ + x ¹⁷ + x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹² - x⁹ - x ⁸ - 2x ⁷ - x ⁶ - x ⁵ + x ² + x + 1

Tugas

Dengan bilangan bulat positif n, kembalikan npolinomial siklomomik ke-10 seperti yang didefinisikan di atas, dalam format yang masuk akal (mis. Daftar koefisien koefisien diperbolehkan).

Aturan

Anda dapat mengembalikan angka floating point / kompleks selama mereka membulatkan ke nilai yang benar.

Mencetak gol

Ini adalah kode-golf . Jawaban terpendek dalam byte menang.

Referensi

• Wolfram MathWorld
• Wikipedia

Haskell , 120 byte

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]

Cobalah online!

Memberikan daftar pelampung kompleks yang memiliki entri seperti 1.0000000000000078 :+ 3.314015728506092e-14karena ketidaklancaran float. Metode penggandaan langsung untuk memulihkan polinomial dari akarnya.

Ini fromIntegeradalah konsesi besar untuk sistem tipe Haskell. Pasti ada cara yang lebih baik. Saran diterima. Berurusan dengan akar persatuan secara simbolis juga mungkin berhasil.

Haskell , 127 byte

(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]

Cobalah online!

Tanpa impor.

Menggunakan formula

Menghitung Φ_n (x) dengan membagi LHS dengan masing-masing istilah lain dalam RHS.

Operator %melakukan pembagian polinomial, mengandalkan sisanya nol. Pembagi dianggap monic, dan diberikan tanpa angka 1, dan juga dengan nol trailing tak terbatas untuk menghindari pemotongan ketika melakukan zipWith.

Mathematica, 43 41 byte

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

Tentu saja, kita selalu dapat menggunakan built-in, tetapi jika tidak, ini akan membagi x ⁿ -1 oleh Φ _k ( x ) (dihitung secara rekursif) untuk setiap pembagi k yang tepat dari n .

Kami menggunakan Factoruntuk mendapatkan polinomial di akhir. Saya pikir alasan ini berhasil adalah karena x^#-1faktor - faktor ke dalam semua polinomial siklotomik pembagi n , dan kemudian kita membagi yang tidak kita inginkan.

-2 byte terima kasih kepada Jenny_mathy, menulis ulang Factorhanya berlaku untuk pembilang.

MATL , 32 31 27 25 byte

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

Output mungkin non-integer karena ketidaktepatan floating-point (yang diizinkan). Footer melakukan pembulatan untuk kejelasan.

Cobalah online!

Haskell , 250 236 233 218 216 byte

Ini adalah versi verbose, (@xnor dapat melakukannya di hampir setengah skor ) tetapi dijamin akan bekerja nselama Anda memiliki cukup memori, tetapi tidak menggunakan builtin untuk menghasilkan polinomial siklomomik ke-n. Input adalah bilangan bulat ukuran arbitrer dan outputnya adalah tipe polinomial dengan koefisien rasional (tepat).

Ide kasar di sini adalah menghitung polinomial secara rekursif. Untuk n=1atau nprima itu sepele. Untuk semua angka lainnya, pendekatan ini pada dasarnya menggunakan rumus dari definisi 2

dipecahkan untuk . Terima kasih @ H.Wiz untuk cukup banyak byte!

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]

Untuk n=105ini menghasilkan polinomial berikut (saya merapikan semua %1penyebut):

[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]

Polinomial n=15015dapat ditemukan di sini (koefisien terbesar adalah 23).

Cobalah online!

Jelly , 23 byte

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

Cobalah online!

Keluaran sebagai daftar koefisien.

Memiliki floating point dan ketidakakuratan yang kompleks. Footer melakukan pembulatan untuk membuat output lebih cantik.

J , 36 bytes

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

Cobalah online!

Menggunakan formula

Ada beberapa ketidakakuratan floating-point, tetapi diizinkan.

Mathematica, 81 byte

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

R , 176 171 139 112 byte

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}

Cobalah online!

Versi yang jauh lebih sederhana; menggunakan forloop daripada a Reduce.

Pari / GP , 8 byte

Built-in.

polcyclo

Cobalah online!

Pari / GP , 39 byte, tanpa built-in

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

Menggunakan rumus:

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

Cobalah online!

CJam ( 52 51 byte)

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

Demo online . Ini adalah blok anonim (fungsi) yang mengambil integer pada stack dan meninggalkan array koefisien endian besar pada stack.

Pembedahan

{                    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
}

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

(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]))}

Penjelasan (Dipilih):

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

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

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

Perhitungan GCD.

h=Math

Karena saya perlu menggunakan fungsi Matematika cukup banyak, saya menggunakan variabel lain di sini.

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

Penggandaan polinomial.

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

Formula yang digunakan adalah

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

Kompres kembali output ke array integer.

Output:

Array bilangan bulat, dengan elemen pada posisi i mewakili koefisien x ^ i.

Salah satu masalah yang dimiliki JS adalah karena JS tidak menyediakan pustaka asli untuk perhitungan pada polinomial dan bilangan kompleks, mereka perlu diimplementasikan dengan cara seperti array.

console.log (phi (105)) memberi

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): Mengubah kode untuk memeriksa nilai yang tidak ditentukan

333> 284 (-49): Mengubah fungsi multiplikasi polinomial karena dapat disederhanakan

284> 277 (-7): Menghapus beberapa kode redundan

277> 265 (-12): Gunakan 2 variabel, bukan array 2-elemen untuk menjatuhkan beberapa byte dalam penggunaan array

265> 264 (-1): Gunakan Array.push () alih-alih Array.concat () untuk mengurangi 4 byte, tetapi menambahkan 3 untuk kurung for-loop dan variabel z

264> 263 (-1): Lebih lanjut bermain golf pada amandemen terakhir

263> 262 (-1): Golf pada for for loop

262> 260 (-2): Keluar dari klausa if

260> 258 (-2): Selanjutnya menggabungkan deklarasi

258> 252 (-6): Bermain golf dengan menggunakan kembali referensi array

252> 250 (-2): Ganti beberapa operator unary sebagai operator biner

250> 245 (-5): Pindahkan kenaikan di Array.map () ke referensi penghitung terakhir untuk menghapus byte

245> 242 (-3): Gunakan sintaksis alih-alih Array.push ()