Hintergrund (zu den Definitionen springen)

Euler hat einen schönen Satz über die komplexen Zahlen bewiesen: e ^ix = cos (x) + i sin (x).

Damit ist der Satz von de Moivre leicht zu beweisen:

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

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

Wir können komplexe Zahlen mit der zweidimensionalen euklidischen Ebene zeichnen, wobei die horizontale Achse den Realteil und die vertikale Achse den Imaginärteil darstellt. Auf diese Weise würde (3,4) der komplexen Zahl 3 + 4i entsprechen.

Wenn Sie mit Polarkoordinaten vertraut sind, wäre (3,4) (5, arctan (4/3)) in Polarkoordinaten. Die erste Zahl r ist der Abstand des Punktes vom Ursprung; die zweite Zahl θ ist der Winkel, der von der positiven x-Achse zum Punkt gegen den Uhrzeigersinn gemessen wird. Infolgedessen ist 3 = r cosθ und 4 = r sinθ. Daher können wir 3 + 4i schreiben als r cosθ + ri sinθ = r (cosθ + i sinθ) = re ^iθ .

Lösen wir die komplexe Gleichung z ⁿ = 1, wobei n eine positive ganze Zahl ist.

Wir lassen z = re ^iθ . Dann z ⁿ = R ⁿ e ^inθ . Der Abstand von Z ⁿ vom Ursprung r ⁿ , und n & theta; der Winkel ist. Wir wissen jedoch, dass der Abstand von 1 vom Ursprung 1 und der Winkel 0 ist. Daher ist r ⁿ = 1 und ⁿ & thgr; = 0. Wenn Sie sich jedoch um 2π mehr drehen, bleiben Sie am selben Punkt, da 2π nur ein voller Kreis ist. Daher ist r = 1 und n & thgr; = 2 k & pgr ;, was uns z = e ^{2ik & pgr; / n ergibt} .

Wir wiederholen unsere Entdeckung: Die Lösungen für z ⁿ = 1 sind z = e ^{2ikπ / n} .

Ein Polynom kann durch seine Wurzeln ausgedrückt werden. Zum Beispiel sind die Wurzeln von x ² -3x + 2 1 und 2, also x ² -3x + 2 = (x-1) (x-2). Ebenso aus unserer Entdeckung oben:

Dieses Produkt enthielt jedoch sicherlich Wurzeln anderer n. Nehmen Sie zum Beispiel n = 8. Die Wurzeln von z ⁴ = 1 würden auch innerhalb der Wurzeln von z ⁸ = 1 enthalten sein, da z ⁴ = 1 z ⁸ = (z ⁴ ) ² = 1 ² = 1 impliziert . Nehmen Sie als Beispiel n = 6. Wenn z ² = 1, dann hätten wir auch z ⁶ = 1. In ähnlicher Weise ist z ⁶ = 1 , wenn z ³ = 1 ist .

Wenn wir die für z ⁿ = 1 eindeutigen Wurzeln extrahieren wollen, brauchen wir k und n, um keinen gemeinsamen Teiler außer 1 zu teilen. Wenn sie sich einen gemeinsamen Teiler d teilen, wobei d> 1 ist, dann wäre z (k) / d) -te Wurzel von z ^{n / d} = 1. Unter Verwendung der obigen Technik, um das Polynom hinsichtlich seiner Wurzeln zu schreiben, erhalten wir das Polynom:

Beachten Sie, dass dieses Polynom durch Entfernen der Wurzeln von z ^{n / d} = 1 erstellt wird, wobei d ein Teiler von n ist. Wir behaupten, dass das obige Polynom ganzzahlige Koeffizienten hat. Betrachten Sie die LCM der Polynome in Form von z ^{n / d} -1, wobei d> 1 und d n dividieren. Die Wurzeln des LCM sind genau die Wurzeln, die wir entfernen möchten. Da jede Komponente ganzzahlige Koeffizienten hat, hat die LCM auch ganzzahlige Koeffizienten. Da die LCM z ⁿ -1 teilt , muss der Quotient ein Polynom mit ganzzahligem Koeffizienten sein, und der Quotient ist das obige Polynom.

Die Wurzeln von z ⁿ = 1 haben alle den Radius 1, bilden also einen Kreis. Das Polynom stellt die Punkte des Kreises dar, die für n eindeutig sind. In gewissem Sinne bilden die Polynome eine Teilung des Kreises. Daher ist das obige Polynom das n-te zyklotomische Polynom. (cyclo- = Kreis; tom- = schneiden)

Definition 1

Die n-te Kreisteilungspolynom, bezeichnet , ist die eindeutige Polynom mit ganzzahligen Koeffizienten , dass divide x ⁿ -1 aber nicht x ^k -1 für k <n.

Definition 2

Die zyklotomischen Polynome sind eine Menge von Polynomen, eine für jede positive ganze Zahl, so dass:

wo k | n bedeutet k dividiert n.

Definition 3

Das n-te zyklotomische Polynom ist das Polynom x ⁿ –1 geteilt durch die LCM der Polynome in der Form x ^k –1, wobei k n und k <n teilt.

Beispiele

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 ⁸ - 2x ⁷ - x ⁶ - x ⁵ + x ² + x + 1

Aufgabe

Bei einer positiven ganzen Zahl nwird das n-te zyklotomische Polynom wie oben definiert in einem vernünftigen Format zurückgegeben (z. B. eine Liste von Koeffizienten ist zulässig).

Regeln

Sie können Gleitkommazahlen / komplexe Zahlen zurückgeben, solange sie auf den richtigen Wert gerundet werden.

Wertung

Das ist Code-Golf . Kürzeste Antwort in Bytes gewinnt.

Verweise

• Wolfram MathWorld
• Wikipedia

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]

Probieren Sie es online!

Gibt eine Liste komplexer Floats mit Einträgen wie 1.0000000000000078 :+ 3.314015728506092e-14 Gleitkommazahlen an , die auf Gleitkommazahlen zurückzuführen sind. Eine direkte Methode zur Multiplikation, um das Polynom aus seinen Wurzeln zu gewinnen.

Das fromInteger ist ein großes Zugeständnis an Haskells Typensystem. Es muss einen besseren Weg geben. Vorschläge sind willkommen. Der symbolische Umgang mit den Wurzeln der Einheit könnte ebenfalls funktionieren.

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]

Probieren Sie es online!

Keine Importe.

Verwendet die Formel

Berechnet Φ_n (x) durch Teilen der LHS durch die anderen Terme in der RHS.

Der Operator %teilt Polynome und verlässt sich darauf, dass der Rest Null ist. Es wird angenommen, dass der Divisor monisch ist, und er wird ohne die führende 1 und mit unendlich nachgestellten Nullen angegeben, um ein Abschneiden zu vermeiden zipWith.

Mathematica, 43 41 Bytes

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

Natürlich können wir immer den eingebauten Teiler verwenden , aber wenn wir dies nicht tun, dividiert dies x ⁿ -1 durch Φ _k ( x ) (rekursiv berechnet) für jeden richtigen Teiler k von n .

Wir verwenden Factor, um am Ende ein Polynom zu erhalten. Ich denke, der Grund, warum dies funktioniert, ist, dass x^#-1Faktoren in alle zyklotomischen Polynome von Teilern von n eingehen und dann diejenigen, die wir nicht wollen, aufgeteilt werden.

-2 Bytes dank Jenny_mathy, das neu geschrieben wurde, Factorum nur für den Zähler zu gelten.

MATL , 32 31 27 25 Bytes

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

Die Ausgabe kann aufgrund von Gleitkommaungenauigkeiten (was zulässig ist) nicht ganzzahlig sein. Die Fußzeile rundet aus Gründen der Übersichtlichkeit.

Probieren Sie es online!

Haskell , 250 236 233 218 216 Bytes

Dies ist eine ausführliche Version, (@xnor kann es in fast tun Hälfte der Partitur ), aber es funktioniert garantiert für jede n, solange Sie genug Speicher haben, aber es verwendet kein eingebautes Element zum Erzeugen des n-ten zyklotomischen Polynoms. Die Eingabe ist eine Ganzzahl beliebiger Größe und die Ausgabe ist ein Polynomtyp mit (exakten) rationalen Koeffizienten.

Die grobe Idee ist hier, die Polynome rekursiv zu berechnen. Für n=1odern prime ist es trivial. Für alle anderen Zahlen verwendet dieser Ansatz grundsätzlich die Formel aus Definition 2

gelöst für . Vielen Dank an H.PWiz für eine Menge 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]

Dafür n=105ergibt sich folgendes Polynom (ich habe alles aufgeräumt%1 Nennern):

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

Das Polynom für n=15015kann gefunden werden hier (der größte Koeffizient 23).

Probieren Sie es online!

Jelly , 23 Bytes

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

Probieren Sie es online!

Ausgabe als Liste von Koeffizienten.

Hat Gleitkomma- UND komplexe Ungenauigkeiten. Die Fußzeile rundet, um die Ausgabe schöner zu machen.

J , 36 Bytes

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

Probieren Sie es online!

Verwendet die Formel

Es gibt einige Gleitkommaungenauigkeiten, die jedoch zulässig sind.

Mathematica, 81 Bytes

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

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}

Probieren Sie es online!

Massiv einfachere Version; verwendet foreher eine Schleife als eine Reduce.

Pari / GP , 8 Bytes

Ein eingebautes.

polcyclo

Probieren Sie es online!

Pari / GP , 39 Bytes, ohne eingebautes

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

Mit der Formel:

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

Probieren Sie es online!

CJam ( 52 51 Bytes)

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

Online-Demo . Dies ist ein anonymer Block (Funktion), der eine Ganzzahl auf dem Stapel annimmt und ein Big-Endian-Array von Koeffizienten auf dem Stapel hinterlässt.

Präparation

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

Erklärung (ausgewählt):

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

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

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

GCD-Berechnung.

h=Math

Da ich viele mathematische Funktionen verwenden muss, habe ich hier eine andere Variable verwendet.

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

Polynom-Multiplikation.

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

Die verwendete Formel lautet

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

Komprimieren Sie die Ausgabe wieder in ein ganzzahliges Array.

Ausgänge:

Ein Array von Ganzzahlen, wobei das Element an Position i den Koeffizienten von x ^ i darstellt.

Ein Problem von JS ist, dass JS keine systemeigene Bibliothek für Berechnungen von Polynomen und komplexen Zahlen bereitstellt und daher eine Array-ähnliche Implementierung benötigt.

console.log (phi (105)) gibt

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): Der Code zum Prüfen undefinierter Werte wurde geändert

333> 284 (-49): Die Polynom-Multiplikationsfunktion wurde geändert, da sie vereinfacht werden kann

284> 277 (-7): Redundanten Code gelöscht

277> 265 (-12): Verwenden Sie 2 Variablen anstelle eines Arrays mit 2 Elementen, um einige Bytes in der Array-Verwendung zu löschen

265> 264 (-1): Verwenden Sie Array.push () anstelle von Array.concat (), um 4 Byte zu reduzieren, fügen Sie jedoch 3 für die Klammern für for-Schleifen und die Variable z hinzu

264> 263 (-1): Bei der letzten Änderung wurde weiter Golf gespielt

263> 262 (-1): Golf auf der for-Schleife

262> 260 (-2): Die if-Klausel wurde entfernt

260> 258 (-2): Weitere Zusammenfassung der Erklärungen

258> 252 (-6): Wird bei Wiederverwendung von Array-Referenzen verwendet

252> 250 (-2): Ersetzen Sie einige unäre Operatoren als binäre Operatoren

250> 245 (-5): Verschieben Sie das Inkrement in Array.map () zur letzten Referenz des Zählers, um Bytes zu entfernen

245> 242 (-3): Verwenden Sie die Spread-Syntax anstelle von Array.push ().