Tło (przejdź do definicji)

Euler udowodnił piękne twierdzenie o liczbach zespolonych: e ^ix = cos (x) + i sin (x).

To sprawia, że ​​twierdzenie de Moivre'a jest łatwe do udowodnienia:

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

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

Możemy rysować liczby zespolone za pomocą dwuwymiarowej płaszczyzny euklidesowej, przy czym oś pozioma reprezentuje część rzeczywistą, a oś pionowa reprezentuje część urojoną. W ten sposób (3,4) odpowiada liczbie zespolonej 3 + 4i.

Jeśli znasz współrzędne biegunowe, (3,4) to (5, arctan (4/3)) we współrzędnych biegunowych. Pierwsza liczba, r, jest odległością punktu od początku; druga liczba, θ, to kąt zmierzony od dodatniej osi x do punktu przeciwnie do ruchu wskazówek zegara. W rezultacie 3 = r cosθ i 4 = r sinθ. Dlatego możemy napisać 3 + 4i jako r cosθ + ri sinθ = r (cosθ + i sinθ) = re ^iθ .

Rozwiążmy równanie zespolone z ⁿ = 1, gdzie n jest liczbą całkowitą dodatnią.

^Pozwalamy z = re ^iθ . Następnie z ⁿ = r ⁿ e ^inθ . Odległość z ⁿ od początku wynosi r ⁿ , a kąt to nθ. Wiemy jednak, że odległość 1 od początku wynosi 1, a kąt wynosi 0. Dlatego r ⁿ = 1 i nθ = 0. Jeśli jednak obrócisz o 2π więcej, nadal skończysz w tym samym punkcie, ponieważ 2π to tylko pełne koło. Dlatego r = 1 i nθ = 2kπ, dając nam z = e ^{2ikπ / n} .

Ponownie odkrywamy nasze odkrycie: rozwiązania z ⁿ = 1 to z = e ^{2ikπ / n} .

Wielomian można wyrazić w kategoriach jego pierwiastków. Na przykład, pierwiastki x ² -3x + 2 to 1 i 2, więc x ² -3x + 2 = (x-1) (x-2). Podobnie z naszego powyższego odkrycia:

Jednak produkt ten z pewnością zawierał korzenie innych n. Na przykład weź n = 8. Korzenie z ⁴ = 1 byłyby również zawarte w rdzeniach z ⁸ = 1, ponieważ z ⁴ = 1 implikuje z ⁸ = (z ⁴ ) ² = 1 ² = 1. Weźmy n = 6 jako przykład. Jeśli z ² = 1, to mielibyśmy również z ⁶ = 1. Podobnie, jeśli z ³ = 1, to z ⁶ = 1.

Jeśli chcemy wyodrębnić pierwiastki unikalne dla z ⁿ = 1, potrzebowalibyśmy k i n, aby nie dzielić wspólnego dzielnika, z wyjątkiem 1. W przeciwnym razie, jeśli dzielą wspólny dzielnik d, gdzie d> 1, to z byłoby (k / d) -ty pierwiastek z ^{n / d} = 1. Używając powyższej techniki do napisania wielomianu w kategoriach jego pierwiastków, otrzymujemy wielomian:

Zauważ, że ten wielomian jest wykonywany przez usunięcie pierwiastków z ^{n / d} = 1, gdzie d jest dzielnikiem n. Twierdzimy, że powyższy wielomian ma współczynniki całkowite. Rozważ LCM wielomianów w postaci z ^{n / d} -1, gdzie d> 1 i d dzieli n. Korzenie LCM są dokładnie korzeniami, które chcemy usunąć. Ponieważ każdy składnik ma współczynniki całkowite, LCM ma również współczynniki całkowite. Ponieważ LCM dzieli z ⁿ -1, iloraz musi być wielomianem o współczynniku całkowitym, a iloraz jest wielomianem powyżej.

Wszystkie pierwiastki z ⁿ = 1 mają promień 1, więc tworzą okrąg. Wielomian reprezentuje punkty koła unikalne dla n, więc w pewnym sensie wielomian tworzy podział koła. Dlatego powyższy wielomian jest n-tym wielomianem cyklotomicznym. (cyklo = koło; tom- = wyciąć)

Definicja 1

N-ty wielomian cyklotomiczny, oznaczony , jest unikalnym wielomianem o współczynnikach całkowitych, które dzielą x ⁿ -1, ale nie x ^k -1 dla k <n.

Definicja 2

Wielomiany cyklotomiczne są zbiorem wielomianów, po jednym dla każdej dodatniej liczby całkowitej, tak że:

gdzie k | n oznacza k dzieli n.

Definicja 3

N-ty cyklotomiczny wielomian jest wielomianem x ⁿ -1 podzielonym przez LCM wielomianów w postaci x ^k -1, gdzie k dzieli n i k <n.

Przykłady

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

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą n, zwróć n-ty wielomian cyklotomowy, jak zdefiniowano powyżej, w rozsądnym formacie (tj. Dozwolona jest lista współczynników).

Zasady

Możesz zwrócić liczby zmiennoprzecinkowe / liczby zespolone, o ile zaokrąglą do prawidłowej wartości.

Punktacja

To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa.

Bibliografia

• Wolfram MathWorld
• Wikipedia

Haskell , 120 bajtów

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]

Wypróbuj online!

Podaje listę złożonych 1.0000000000000078 :+ 3.314015728506092e-14operacji zmiennoprzecinkowych, które zawierają wpisy podobne do niedokładności zmiennoprzecinkowych. Bezpośrednia metoda mnożenia w celu odzyskania wielomianu z jego pierwiastków.

fromIntegerJest wielkim ustępstwem na rzecz systemu typu Haskell'a. Musi być lepszy sposób. Sugestie są mile widziane. Symboliczne podejście do korzeni jedności może również działać.

Haskell , 127 bajtów

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

Wypróbuj online!

Bez importu.

Korzysta ze wzoru

Oblicza Φ_n (x) dzieląc LHS przez każdy z pozostałych terminów w RHS.

Operator %dokonuje podziału na wielomianach, opierając się na pozostałej wartości równej zero. Zakłada się, że dzielnik jest moniczny i jest podawany bez wiodącego 1, a także z nieskończonymi końcowymi zerami, aby uniknąć obcięcia podczas działania zipWith.

Mathematica, 43 41 bajtów

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

Oczywiście, zawsze możemy skorzystać z wbudowanej, ale jeśli tego nie zrobimy, Dzieli x ⁿ -1 przez cp _k ( x ) (obliczonej rekursywnie) dla każdego właściwego dzielnika k od n .

Na końcu Factorotrzymujemy wielomian. Myślę, że powodem tego jest to, że x^#-1uwzględnia wszystkie cyklomomiczne wielomiany dzielników n , a następnie dzielimy te, których nie chcemy.

-2 bajty dzięki Jenny_mathy, przepisując, Factoraby dotyczyła tylko licznika.

MATL , 32 31 27 25 bajtów

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

Wyjście może nie być liczbą całkowitą z powodu niedokładności zmiennoprzecinkowych (co jest dozwolone). Stopka zaokrągla dla przejrzystości.

Wypróbuj online!

Haskell , 250 236 233 218 216 bajtów

To jest wersja pełna (@xnor może to zrobić w prawie połowie wyniku ), ale gwarantuje, że będzie działała ntak długo, jak masz wystarczającą ilość pamięci, ale nie używa wbudowanego do generowania n-tego cyklomomicznego wielomianu. Dane wejściowe są liczbami całkowitymi o dowolnym rozmiarze, a dane wyjściowe są typami wielomianowymi o (dokładnych) współczynnikach wymiernych.

Szorstki pomysł polega na obliczaniu wielomianów rekurencyjnie. Dla n=1lub npierwszej jest to banalne. W przypadku wszystkich innych liczb to podejście zasadniczo wykorzystuje wzór z definicji 2

rozwiązany dla . Dzięki @ H.PWiz za całkiem sporo bajtów!

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]

Dla n=105tego uzyskuje się następujący wielomian (uporządkowałem wszystkie %1mianowniki):

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

Wielomian dla n=15015można znaleźć tutaj (największy współczynnik wynosi 23).

Wypróbuj online!

Galaretka , 23 bajty

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

Wypróbuj online!

Dane wyjściowe jako lista współczynników.

Ma zmiennoprzecinkowe ORAZ złożone niedokładności. Stopka zaokrągla, aby wydruk był ładniejszy.

J , 36 bajtów

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

Wypróbuj online!

Korzysta ze wzoru

Istnieją pewne niedokładności zmiennoprzecinkowe, ale jest to dozwolone.

Mathematica, 81 bajtów

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

R , 176 171 139 112 bajtów

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}

Wypróbuj online!

Znacznie prostsza wersja; używa forpętli zamiast Reduce.

Pari / GP , 8 bajtów

Wbudowany.

polcyclo

Wypróbuj online!

Pari / GP , 39 bajtów, bez wbudowanego

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

Za pomocą wzoru:

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

Wypróbuj online!

CJam ( 52 51 bajtów)

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

Demo online . Jest to anonimowy blok (funkcja), który przyjmuje liczbę całkowitą na stos i pozostawia tablicę współczynników big-endian na stosie.

Sekcja

{                    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 bajtów

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

Objaśnienie (wybrane):

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

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

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

Obliczanie GCD.

h=Math

Ponieważ muszę dość często korzystać z funkcji matematycznych, użyłem tutaj innej zmiennej.

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

Mnożenie wielomianowe.

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

Zastosowana formuła to

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

Kompresuj dane wyjściowe z powrotem do tablicy liczb całkowitych.

Wyjścia:

Tablica liczb całkowitych, z elementem w pozycji i reprezentującym współczynnik x ^ i.

Jednym z problemów JS jest to, że ponieważ JS nie zapewnia biblioteki natywnej do obliczeń wielomianów i liczb zespolonych, musiały zostać zaimplementowane w sposób tablicowy.

console.log (phi (105)) daje

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): Zmieniono kod sprawdzania niezdefiniowanej wartości

333> 284 (-49): Zmieniono funkcję mnożenia wielomianu, ponieważ można ją uprościć

284> 277 (-7): Usunięto zbędny kod

277> 265 (-12): Użyj 2 zmiennych zamiast 2-elementowej tablicy, aby upuścić niektóre bajty w użyciu tablicy

265> 264 (-1): Użyj Array.push () zamiast Array.concat (), aby zmniejszyć 4 bajty, ale dodano 3 dla nawiasów klamrowych for i zmiennej z

264> 263 (-1): Dalsza gra w golfa przy ostatniej poprawce

263> 262 (-1): Gra w golfa na pętli for

262> 260 (-2): Grał w klauzulę if

260> 258 (-2): Dalsze połączenie deklaracji

258> 252 (-6): Gra w golfa przy ponownym użyciu odwołań do tablicy

252> 250 (-2): zamień niektóre operatory jednoargumentowe na operatory binarne

250> 245 (-5): Przenieś przyrost w Array.map () do ostatniego odwołania licznika, aby usunąć bajty

245> 242 (-3): Użyj składni spreadu zamiast Array.push ()