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 ) n = e i (nx)
(cos (x) + i sin (x)) n = 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 n = 1, gdzie n jest liczbą całkowitą dodatnią.
Pozwalamy z = re iθ . Następnie z n = r n e inθ . Odległość z n od początku wynosi r n , a kąt to nθ. Wiemy jednak, że odległość 1 od początku wynosi 1, a kąt wynosi 0. Dlatego r n = 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 n = 1 to z = e 2ikπ / n .
Wielomian można wyrazić w kategoriach jego pierwiastków. Na przykład, pierwiastki x 2 -3x + 2 to 1 i 2, więc x 2 -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 4 = 1 byłyby również zawarte w rdzeniach z 8 = 1, ponieważ z 4 = 1 implikuje z 8 = (z 4 ) 2 = 1 2 = 1. Weźmy n = 6 jako przykład. Jeśli z 2 = 1, to mielibyśmy również z 6 = 1. Podobnie, jeśli z 3 = 1, to z 6 = 1.
Jeśli chcemy wyodrębnić pierwiastki unikalne dla z n = 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 n -1, iloraz musi być wielomianem o współczynniku całkowitym, a iloraz jest wielomianem powyżej.
Wszystkie pierwiastki z n = 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 n -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 n -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 2 + x + 1
- Φ 30 (x) = x 8 + x 7 - x 5 - x 4 - x 3 + x + 1
- Φ 105 (x) = x 48 + x 47 + x 46 - x 43 - x 42 - 2x 41 - x 40 - x 39 + x 36 + x 35 + x 34 + x 33 + x 32 + x 31 - x 28 - x 26 - x 24 - x 22 - x 20 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 - x9 - x 8 - 2x 7 - x 6 - x 5 + x 2 + 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
źródło
Odpowiedzi:
Haskell , 120 bajtów
Wypróbuj online!
Podaje listę złożonych
1.0000000000000078 :+ 3.314015728506092e-14
operacji zmiennoprzecinkowych, które zawierają wpisy podobne do niedokładności zmiennoprzecinkowych. Bezpośrednia metoda mnożenia w celu odzyskania wielomianu z jego pierwiastków.fromInteger
Jest 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
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łaniazipWith
.źródło
[0,0..]
jest bajtem krótszym niżrepeat 0
.Mathematica,
4341 bajtówOczywiście, zawsze możemy skorzystać z wbudowanej, ale jeśli tego nie zrobimy, Dzieli x n -1 przez cp k ( x ) (obliczonej rekursywnie) dla każdego właściwego dzielnika k od n .
Na końcu
Factor
otrzymujemy wielomian. Myślę, że powodem tego jest to, żex^#-1
uwzględnia wszystkie cyklomomiczne wielomiany dzielników n , a następnie dzielimy te, których nie chcemy.-2 bajty dzięki Jenny_mathy, przepisując,
Factor
aby dotyczyła tylko licznika.źródło
Factor@
Factor[x^#-1]/Times@@...
zamiast; gdybyśmy nie mieli nawiasów, chcielibyśmy nawiasów.Factor[x^#-1]/Times@@...
, a także oznacza, że nie mam pojęcia, jak to działa.MATL ,
32312725 bajtówWyjś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!
źródło
Haskell ,
250 236 233 218216 bajtówTo jest wersja pełna (@xnor może to zrobić w prawie połowie wyniku ), ale gwarantuje, że będzie działała
n
tak 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=1
lubn
pierwszej jest to banalne. W przypadku wszystkich innych liczb to podejście zasadniczo wykorzystuje wzór z definicji 2rozwiązany dla . Dzięki @ H.PWiz za całkiem sporo bajtów!
Dla
n=105
tego uzyskuje się następujący wielomian (uporządkowałem wszystkie%1
mianowniki):Wielomian dla
n=15015
można znaleźć tutaj (największy współczynnik wynosi 23).Wypróbuj online!
źródło
+1
za to, że nie jest wbudowany.Rationals
? Wydaje się, że bez nich działa dobrzequotRemPoly
, pozwól mi spróbować jeszcze raz!Double
współczynniki, jeśli nie użyjesz goRatio Integer
zamiast tego, co może powodować problemy dla bardzo (bardzo) dużychn
.Galaretka , 23 bajty
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.
źródło
J , 36 bajtów
Wypróbuj online!
Korzysta ze wzoru
Istnieją pewne niedokładności zmiennoprzecinkowe, ale jest to dozwolone.
źródło
Mathematica, 81 bajtów
źródło
R ,
176171139112 bajtówWypróbuj online!
Znacznie prostsza wersja; używa
for
pętli zamiastReduce
.źródło
Pari / GP , 8 bajtów
Wbudowany.
Wypróbuj online!
Pari / GP , 39 bajtów, bez wbudowanego
Za pomocą wzoru:
Wypróbuj online!
źródło
CJam (
5251 bajtów)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
źródło
JavaScript (ES6),
337333284...252250245242 bajtówObjaśnienie (wybrane):
Zainicjuj z = (1 + 0i) * x ^ 0
Obliczanie GCD.
Ponieważ muszę dość często korzystać z funkcji matematycznych, użyłem tutaj innej zmiennej.
Mnożenie wielomianowe.
Zastosowana formuła to
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
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 ()
źródło