Un polinomio con coeficientes en algún campo F se llama irreducible sobre F si no se puede descomponer en el producto de polinomios de grado más bajas con coeficientes en F .
Considere polinomios sobre el campo de Galois GF (5). Este campo contiene 5 elementos, a saber, los números 0, 1, 2, 3 y 4.
Tarea
Dado un número entero positivo n , calcule el número de polinomios irreducibles de grado n sobre GF (5). Estos son simplemente los polinomios con coeficientes en 0-4 que no pueden factorizarse en otros polinomios con coeficientes en 0-4.
Entrada
La entrada será un entero único y puede provenir de cualquier fuente estándar (por ejemplo, STDIN o argumentos de función). Debe admitir la entrada hasta el entero más grande de modo que la salida no se desborde.
Salida
Imprima o devuelva el número de polinomios que son irreducibles sobre GF (5). Tenga en cuenta que estos números aumentan bastante rápido.
Ejemplos
In : Out
1 : 5
2 : 10
3 : 40
4 : 150
5 : 624
6 : 2580
7 : 11160
8 : 48750
9 : 217000
10 : 976248
11 : 4438920
Tenga en cuenta que estos números forman la secuencia A001692 en OEIS.
fuente
Respuestas:
Gelatina ,
30232220 bytesPruébalo en línea! o verificar todos los casos de prueba a la vez .
Algoritmo
Esto usa la fórmula
de la página OEIS, donde d | n indica que sumamos sobre todos los divisores d de n , y μ representa la función de Möbius .
Código
fuente
Mathematica,
3938 bytesUtiliza la misma fórmula que la respuesta Jelly.
fuente
DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]&
Pari / GP , 17 bytes
Pruébalo en línea!
Pari / GP , sin incorporado, 35 bytes
Pruébalo en línea!
fuente