Wielomian cyklotomiczny

17

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 .

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

Pozwalamy z = re . 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. Φ 1 (x) = x - 1
  2. Φ 2 (x) = x + 1
  3. Φ 3 (x) = x 2 + x + 1
  4. Φ 30 (x) = x 8 + x 7 - x 5 - x 4 - x 3 + x + 1
  5. Φ 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 . Najkrótsza odpowiedź w bajtach wygrywa.

Bibliografia

Leaky Nun
źródło
1
Może dodać 105 jako test?
Jonathan Allan
@JonathanAllan Nie chcę wpisywać 48 terminów
Leaky Nun
1
Czy dozwolone są niedokładności zmiennoprzecinkowe?
mile
3
@miles Nienawidzę pływać z pasją>. <ale będę bronił do śmierci twojego prawa do używania pływaków.
Leaky Nun
1
Czy możemy wyprowadzać złożone liczby zmiennoprzecinkowe, o ile dają poprawną odpowiedź po zaokrągleniu do najbliższej liczby całkowitej / liczby Gaussa?
fireflame241

Odpowiedzi:

12

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.

xnor
źródło
[0,0..]jest bajtem krótszym niż repeat 0.
Laikoni
@flawr Dzieli wielomiany. Myślę, że to ta sama metoda, co twoje rozwiązanie.
xnor
Wygląda cholernie elegancko, jutro będę musiał przyjrzeć się bliżej :)
flawr
ta odpowiedź sprawia, że ​​chcę się uczyć Haskell.
Giuseppe
1
@xnor -1 bajt
H.PWiz
7

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 n -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.

Misza Ławrow
źródło
2
To jest świetne! możesz zapisać bajt, używającFactor@
J42161217
@Jenny_mathy Robi to wydaje się parsować jak Factor[x^#-1]/Times@@...zamiast; gdybyśmy nie mieli nawiasów, chcielibyśmy nawiasów.
Misha Lavrov
1
ok ... ale muszę powiedzieć, że kiedy go testowałem, dawał właściwe wyniki ...
J42161217
To interesujące. Oznacza to, że możemy zapisać kolejny bajt, pisząc go Factor[x^#-1]/Times@@..., a także oznacza, że ​​nie mam pojęcia, jak to działa.
Misha Lavrov
5

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!

Luis Mendo
źródło
4

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!

wada
źródło
+1za to, że nie jest wbudowany.
DJMcMayhem
@flawr Dlaczego używasz Rationals? Wydaje się, że bez nich działa dobrze
H.PWiz
Czy to? Miałem problemy quotRemPoly, pozwól mi spróbować jeszcze raz!
flawr
Ach, „problemem” było to, że daje Doublewspółczynniki, jeśli nie użyjesz go Ratio Integerzamiast tego, co może powodować problemy dla bardzo (bardzo) dużych n.
flawr
Ech ... Nie sądzę, żeby to był problem.
H.PWiz
3

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.

fireflame241
źródło
3

J , 36 bajtów

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

Wypróbuj online!

Korzysta ze wzoru

formuła

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

mile
źródło
2

Mathematica, 81 bajtów

Round@CoefficientList[Times@@(x-E^(2Pi*I#/k)&/@Select[Range[k=#],#~GCD~k<2&]),x]&
J42161217
źródło
2

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.

Giuseppe
źródło
2

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:

Φn(x)=xn-1re<nre|nΦre(x).

Wypróbuj online!

alephalpha
źródło
1

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
}
Peter Taylor
źródło
0

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

wprowadź opis zdjęcia tutaj

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

Shieru Asakoto
źródło