Antecedentes (salte a las definiciones)
Euler demostró un hermoso teorema sobre los números complejos: e ix = cos (x) + i sin (x).
Esto hace que el teorema de de Moivre sea fácil de probar:
(e ix ) n = e i (nx)
(cos (x) + i sen (x)) n = cos (nx) + i sin (nx)
Podemos trazar números complejos usando el plano euclidiano bidimensional, donde el eje horizontal representa la parte real y el eje vertical representa la parte imaginaria. De esta manera, (3,4) correspondería al número complejo 3 + 4i.
Si está familiarizado con las coordenadas polares, (3,4) sería (5, arctan (4/3)) en coordenadas polares. El primer número, r, es la distancia del punto desde el origen; el segundo número, θ, es el ángulo medido desde el eje x positivo hasta el punto, en sentido antihorario. Como resultado, 3 = r cosθ y 4 = r sinθ. Por lo tanto, podemos escribir 3 + 4i como r cosθ + ri sinθ = r (cosθ + i sinθ) = re iθ .
Resolvamos la ecuación compleja z n = 1, donde n es un número entero positivo.
Dejamos z = re iθ . Entonces, z n = r n e inθ . La distancia de z n desde el origen es r n , y el ángulo es nθ. Sin embargo, sabemos que la distancia de 1 desde el origen es 1 y el ángulo es 0. Por lo tanto, r n = 1 y nθ = 0. Sin embargo, si giras 2π más, aún terminas en el mismo punto, porque 2π es solo un círculo completo. Por lo tanto, r = 1 y nθ = 2kπ, dándonos z = e 2ikπ / n .
Replanteamos nuestro descubrimiento: las soluciones para z n = 1 son z = e 2ikπ / n .
Un polinomio se puede expresar en términos de sus raíces. Por ejemplo, las raíces de x 2 -3x + 2 son 1 y 2, entonces x 2 -3x + 2 = (x-1) (x-2). Del mismo modo, de nuestro descubrimiento anterior:
Sin embargo, ese producto ciertamente contenía raíces de otros n. Por ejemplo, tome n = 8. Las raíces de z 4 = 1 también se incluirían dentro de las raíces de z 8 = 1, ya que z 4 = 1 implica z 8 = (z 4 ) 2 = 1 2 = 1. Tome n = 6 como ejemplo. Si z 2 = 1, entonces también tendríamos z 6 = 1. Del mismo modo, si z 3 = 1, entonces z 6 = 1.
Si queremos extraer las raíces exclusivas de z n = 1, necesitaríamos k y n para no compartir ningún divisor común excepto 1. O bien, si comparten un divisor común d donde d> 1, entonces z sería el (k / d) enésima raíz de z n / d = 1. Usando la técnica anterior para escribir el polinomio en términos de sus raíces, obtenemos el polinomio:
Tenga en cuenta que este polinomio se realiza eliminando las raíces de z n / d = 1 con d siendo un divisor de n. Afirmamos que el polinomio anterior tiene coeficientes enteros. Considere el MCM de los polinomios en forma de z n / d -1 donde d> 1 yd divide n. Las raíces del LCM son exactamente las raíces que deseamos eliminar. Como cada componente tiene coeficientes enteros, el LCM también tiene coeficientes enteros. Como el MCM divide z n -1, el cociente debe ser un polinomio con coeficiente entero, y el cociente es el polinomio anterior.
Las raíces de z n = 1 tienen radio 1, por lo que forman un círculo. El polinomio representa los puntos del círculo únicos de n, por lo que, en cierto sentido, los polinomios forman una partición del círculo. Por lo tanto, el polinomio anterior es el enésimo polinomio ciclotómico. (ciclo- = círculo; tom- = cortar)
Definición 1
El enésimo polinomio ciclotómico, denotado , es el polinomio único con coeficientes enteros que divide x n -1 pero no x k -1 para k <n.
Definición 2
Los polinomios ciclotómicos son un conjunto de polinomios, uno para cada entero positivo, de modo que:
donde k | n significa k divide n.
Definición 3
El polinomio ciclotómico n-ésimo es el polinomio x n -1 dividido por el LCM de los polinomios en la forma x k -1 donde k divide n y k <n.
Ejemplos
- Φ 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 - x8 - 2x 7 - x 6 - x 5 + x 2 + x + 1
Tarea
Dado un entero positivo n
, devuelve eln
polinomio ciclotómico -th como se definió anteriormente, en un formato razonable (es decir, se permite una lista de coeficientes).
Reglas
Puede devolver números flotantes / complejos siempre que se redondeen al valor correcto.
Puntuación
Esto es código golf . La respuesta más corta en bytes gana.
Referencias
fuente
Respuestas:
Haskell , 120 bytes
Pruébalo en línea!
Da una lista de flotadores complejos que tiene entradas como
1.0000000000000078 :+ 3.314015728506092e-14
debido a la falta de capacidad de flotación. Un método directo de multiplicación para recuperar el polinomio desde sus raíces.El
fromInteger
es una gran concesión al sistema de tipos de Haskell. Tiene que haber una mejor manera. Las sugerencias son bienvenidas. Tratar simbólicamente con las raíces de la unidad también podría funcionar.Haskell , 127 bytes
Pruébalo en línea!
Sin importaciones
Usa la fórmula
Calcula Φ_n (x) dividiendo el LHS por cada uno de los otros términos en el RHS.
El operador
%
hace la división en polinomios, confiando en que el resto sea cero. Se supone que el divisor es monic, y se da sin el 1 inicial, y también con ceros finales infinitos para evitar truncarse al hacerlozipWith
.fuente
[0,0..]
es un byte más corto querepeat 0
.Mathematica,
4341 bytesPor supuesto, siempre podemos usar el incorporado, pero si no lo hacemos, esto divide x n -1 por Φ k ( x ) (calculado recursivamente) para cada divisor apropiado k de n .
Usamos
Factor
para obtener un polinomio al final. Creo que la razón por la que esto funciona es que tienex^#-1
en cuenta todos los polinomios ciclotómicos de los divisores de n , y luego dividimos los que no queremos.-2 bytes gracias a Jenny_mathy, reescribiendo
Factor
para que solo se aplique al numerador.fuente
Factor@
Factor[x^#-1]/Times@@...
lugar; si no tuviéramos paréntesis, querríamos paréntesis.Factor[x^#-1]/Times@@...
, y también significa que no tengo idea de cómo funciona.MATL ,
32312725 bytesLa salida puede ser no entera debido a imprecisiones de punto flotante (que está permitido). El pie de página hace redondeo para mayor claridad.
Pruébalo en línea!
fuente
Haskell ,
250 236 233 218216 bytesEsta es una versión detallada, (@xnor puede hacerlo en casi la mitad del puntaje ) pero está garantizado que funcionará para cualquier
n
siempre que tenga suficiente memoria, pero no utiliza un generador incorporado para generar el polinomio ciclotómico n-ésimo. La entrada es un número entero de tamaño arbitrario y la salida es de tipo polinomial con coeficientes racionales (exactos).La idea aproximada aquí es calcular los polinomios de forma recursiva. Para
n=1
on
primo es trivial. Para todos los demás números, este enfoque utiliza básicamente la fórmula de la definición 2resuelto por . ¡Gracias @ H.PWiz por un montón de bytes!
Para
n=105
esto se obtiene el siguiente polinomio (ordené todos los%1
denominadores):El polinomio para
n=15015
se puede encontrar aquí (el coeficiente más grande es 23).Pruébalo en línea!
fuente
+1
por no ser un empotrado.Rationals
? Parece funcionar bien sin ellosquotRemPoly
, ¡déjame intentarlo de nuevo!Double
coeficientes si no los usaRatio Integer
, lo que podría causar problemas para muy (muy) grandesn
.Jalea , 23 bytes
Pruébalo en línea!
Salidas como una lista de coeficientes.
Tiene coma flotante e inexactitudes complejas. El pie de página se redondea para que la salida sea más bonita.
fuente
J , 36 bytes
Pruébalo en línea!
Usa la fórmula
Hay algunas imprecisiones de coma flotante, pero está permitido.
fuente
Mathematica, 81 bytes
fuente
R ,
176171139112 bytesPruébalo en línea!
Versión masivamente simple; usa un
for
bucle en lugar de unReduce
.fuente
Pari / GP , 8 bytes
Un incorporado.
Pruébalo en línea!
Pari / GP , 39 bytes, sin incorporado
Usando la fórmula:
Pruébalo en línea!
fuente
CJam (
5251 bytes)Demostración en línea . Este es un bloque anónimo (función) que toma un número entero en la pila y deja una matriz big-endian de coeficientes en la pila.
Disección
fuente
JavaScript (ES6),
337333284...252250245242 bytesExplicación (Seleccionada):
Inicializar z = (1 + 0i) * x ^ 0
Cálculo de MCD.
Como necesito usar muchas funciones matemáticas, usé otra variable aquí.
Multiplicación polinómica.
La fórmula utilizada es
Comprima la salida nuevamente a una matriz entera.
Salidas:
Una matriz de enteros, con el elemento en la posición i representando el coeficiente de x ^ i.
Uno de los problemas que tiene JS es que, dado que JS no proporciona una biblioteca nativa para los cálculos de polinomios y números complejos, era necesario implementarlos de forma similar a una matriz.
console.log (phi (105)) da
337> 333 (-4): se modificó el código para verificar el valor indefinido
333> 284 (-49): se modificó la función de multiplicación polinómica porque se puede simplificar
284> 277 (-7): eliminado algún código redundante
277> 265 (-12): use 2 variables en lugar de una matriz de 2 elementos para eliminar algunos bytes en el uso de la matriz
265> 264 (-1): use Array.push () en lugar de Array.concat () para reducir 4 bytes, pero agregó 3 para los corchetes for-loop y la variable z
264> 263 (-1): más golf en la última enmienda
263> 262 (-1): Golf en el bucle for
262> 260 (-2): Golfed la cláusula if
260> 258 (-2): combina aún más las declaraciones
258> 252 (-6): Golf en la reutilización de referencias de matriz
252> 250 (-2): reemplazar algunos operadores unarios como operadores binarios
250> 245 (-5): mueva el incremento en Array.map () a la última referencia del contador para eliminar bytes
245> 242 (-3): utilice la sintaxis de propagación en lugar de Array.push ()
fuente