Segundo plano (pule para definições)

Euler provou um belo teorema sobre os números complexos: e ^ix = cos (x) + i sin (x).

Isso facilita a prova do teorema de De Moivre:

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

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

Podemos plotar números complexos usando o plano euclidiano bidimensional, com o eixo horizontal representando a parte real e o eixo vertical representando a parte imaginária. Dessa forma, (3,4) corresponderia ao número complexo 3 + 4i.

Se você estiver familiarizado com as coordenadas polares, (3,4) seria (5, arctan (4/3)) nas coordenadas polares. O primeiro número, r, é a distância do ponto da origem; o segundo número, θ, é o ângulo medido do eixo x positivo ao ponto no sentido anti-horário. Como resultado, 3 = r cosθ e 4 = r sinθ. Portanto, podemos escrever 3 + 4i como r cosθ + ri sinθ = r (cosθ + i sinθ) = re ^iθ .

Vamos resolver a equação complexa z ⁿ = 1, onde n é um número inteiro positivo.

Deixamos z = re ^iθ . Então, z ⁿ = r ⁿ e ^inθ . A distância de z ⁿ da origem é r ⁿ , e o ângulo é nθ. No entanto, sabemos que a distância de 1 da origem é 1 e o ângulo é 0. Portanto, r ⁿ = 1 e nθ = 0. No entanto, se você girar mais 2π, ainda terminará no mesmo ponto, porque 2π é apenas um círculo completo. Portanto, r = 1 e nθ = 2kπ, dando-nos z = e ^{2ikπ / n} .

Reafirmamos nossa descoberta: as soluções para z ⁿ = 1 são z = e ^{2ikπ / n} .

Um polinômio pode ser expresso em termos de suas raízes. Por exemplo, as raízes de x ² -3x + 2 são 1 e 2, então x ² -3x + 2 = (x-1) (x-2). Da mesma forma, de nossa descoberta acima:

No entanto, esse produto certamente continha raízes de outros n. Por exemplo, considere n = 8. As raízes de z ⁴ = 1 também seriam incluídas nas raízes de z ⁸ = 1, uma vez que z ⁴ = 1 implica z ⁸ = (z ⁴ ) ² = 1 ² = 1. Tome n = 6 como exemplo. Se z ² = 1, também teríamos z ⁶ = 1. Da mesma forma, se z ³ = 1, então z ⁶ = 1.

Se quisermos extrair as raízes exclusivas de z ⁿ = 1, precisaríamos de k e n para não compartilhar nenhum divisor comum, exceto 1. Caso contrário, se eles compartilharem um divisor comum d, em que d> 1, z seria o (k / d) -ésima raiz de z ^{n / d} = 1. Usando a técnica acima para escrever o polinômio em termos de suas raízes, obtemos o polinômio:

Observe que esse polinômio é feito removendo as raízes de z ^{n / d} = 1, com d sendo um divisor de n. Afirmamos que o polinômio acima tem coeficientes inteiros. Considere o LCM dos polinômios na forma de z ^{n / d} -1, em que d> 1 ed divide n. As raízes do LCM são exatamente as que queremos remover. Como cada componente possui coeficientes inteiros, o LCM também possui coeficientes inteiros. Como o LCM divide z ⁿ -1, o quociente deve ser um polinômio com coeficiente inteiro, e o quociente é o polinômio acima.

As raízes de z ⁿ = 1 têm raio 1 e formam um círculo. O polinômio representa os pontos do círculo exclusivos de n; portanto, em certo sentido, os polinômios formam uma partição do círculo. Portanto, o polinômio acima é o n-ésimo polinômio ciclotômico. (ciclo- = círculo; tom- = cortar)

Definição 1

O n-ésimo polinômio ciclotômico, denotado , é o polinômio único com coeficientes inteiros que dividem x ⁿ -1, mas não x ^k -1 para k <n.

Definição 2

Os polinômios ciclotômicos são um conjunto de polinômios, um para cada número inteiro positivo, de modo que:

onde k | n significa k divide n.

Definição 3

O n-ésimo polinômio ciclotômico é o polinômio x ⁿ -1 dividido pelo LCM dos polinômios na forma x ^k -1 em que k divide n e k <n.

Exemplos

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

Tarefa

Dado um número inteiro positivo n, retorne o n-ésimo polinômio ciclotômico conforme definido acima, em um formato razoável (por exemplo, é permitida uma lista de coeficientes).

Regras

Você pode retornar números flutuantes / complexos, contanto que arredondem para o valor correto.

Pontuação

Isso é código-golfe . A resposta mais curta em bytes vence.

Referências

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

Experimente online!

Fornece uma lista de carros alegóricos complexos com entradas como 1.0000000000000078 :+ 3.314015728506092e-14devido à imprecisão do carro alegórico. Um método direto de multiplicar para recuperar o polinômio de suas raízes.

A fromIntegeré uma grande concessão ao sistema de tipos da Haskell. Tem que haver uma maneira melhor. Sugestões são bem vindas. Lidar com raízes da unidade simbolicamente também pode funcionar.

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]

Experimente online!

Sem importações.

Usa a fórmula

Calcula Φ_n (x) dividindo o LHS por cada um dos outros termos no RHS.

O operador %faz divisão em polinômios, contando com o restante sendo zero. Supõe-se que o divisor seja monônico e é fornecido sem o 1 inicial, e também com zeros à direita infinitos para evitar truncamento ao fazer zipWith.

Mathematica, 43 41 bytes

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

Obviamente, sempre podemos usar o built-in, mas se não o fizermos, isso divide x ⁿ -1 por Φ _k ( x ) (calculado recursivamente) para cada divisor adequado k de n .

Usamos Factorpara obter um polinômio no final. Penso que a razão pela qual isso funciona é o x^#-1fator de todos os polinômios ciclotômicos dos divisores de n , e então dividimos os que não queremos.

-2 bytes graças a Jenny_mathy, reescrevendo Factorpara aplicar somente ao numerador.

MATL , 32 31 27 25 bytes

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

A saída pode não ser um número inteiro devido a imprecisões de ponto flutuante (o que é permitido). O rodapé faz arredondamentos para maior clareza.

Experimente online!

Haskell , 250 236 233 218 216 bytes

Esta é uma versão detalhada (o @xnor pode fazê-lo em quase metade da pontuação ), mas é garantido que funcione por ntanto tempo quanto você tiver memória suficiente, mas não usa um built-in para gerar o n-ésimo polinômio ciclotômico. A entrada é um número inteiro de tamanho arbitrário e a saída é do tipo polinomial com coeficientes racionais (exatos).

A idéia aproximada aqui é calcular os polinômios recursivamente. Para n=1ou nprime, é trivial. Para todos os outros números, essa abordagem basicamente usa a fórmula da definição 2

resolvido para . Obrigado @ H.PWiz por um monte de 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]

Para n=105isso, obtém-se o seguinte polinômio (arrumei todos os %1denominadores):

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

O polinômio para n=15015pode ser encontrado aqui (o maior coeficiente é 23).

Experimente online!

Gelatina , 23 bytes

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

Experimente online!

Saídas como uma lista de coeficientes.

Possui ponto flutuante E imprecisões complexas. O rodapé faz o arredondamento para tornar a saída mais bonita.

J , 36 bytes

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

Experimente online!

Usa a fórmula

Existem algumas imprecisões de ponto flutuante, mas isso é permitido.

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}

Experimente online!

Versão massivamente mais simples; usa um forloop em vez de a Reduce.

Pari / GP , 8 bytes

Um embutido.

polcyclo

Experimente online!

Pari / GP , 39 bytes, sem built-in

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

Usando a fórmula:

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

Experimente online!

CJam ( 52 51 bytes)

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

Demonstração online . Este é um bloco anônimo (função) que pega um número inteiro na pilha e deixa uma matriz big-endian de coeficientes na pilha.

Dissecação

{                    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 bytes

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

Explicação (selecionada):

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

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

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

Cálculo GCD.

h=Math

Como preciso usar bastante as funções de matemática, usei outra variável aqui.

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

Multiplicação polinomial.

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

A fórmula usada é

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

Comprima a saída de volta para uma matriz inteira.

Saídas:

Uma matriz de números inteiros, com o elemento na posição i representando o coeficiente de x ^ i.

Um dos problemas que JS tem é que, como o JS não fornece biblioteca nativa para cálculos em polinômios e números complexos, eles precisavam ser implementados de maneira semelhante a um array.

console.log (phi (105)) fornece

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): foi alterado o código para verificar o valor indefinido

333> 284 (-49): alterada a função de multiplicação polinomial porque pode ser simplificada

284> 277 (-7): excluído algum código redundante

277> 265 (-12): use 2 variáveis ​​em vez de uma matriz de 2 elementos para eliminar alguns bytes no uso da matriz

265> 264 (-1): use Array.push () em vez de Array.concat () para reduzir 4 bytes, mas adicionou 3 para as chaves de loop for e a variável z

264> 263 (-1): Mais golfe na última alteração

263> 262 (-1): jogou golfe no loop for

262> 260 (-2): aplicou a cláusula if

260> 258 (-2): combinação adicional das declarações

258> 252 (-6): Golfe na reutilização de referências de matriz

252> 250 (-2): Substitua alguns operadores unários como operadores binários

250> 245 (-5): mova o incremento em Array.map () para a última referência do contador para remover bytes

245> 242 (-3): use a sintaxe de propagação em vez de Array.push ()