Un polynôme à coefficients dans certains champ F est appelé irréductible sur F si elle ne peut être décomposé en produit de polynômes de degré inférieur à coefficients dans F .

Considérons les polynômes sur le champ de Galois GF (5). Ce champ contient 5 éléments, à savoir les nombres 0, 1, 2, 3 et 4.

Tâche

Étant donné un entier positif n , calculer le nombre de polynômes irréductibles de degré n sur GF (5). Ce sont simplement les polynômes avec des coefficients en 0-4 qui ne peuvent pas être pris en compte dans d'autres polynômes avec des coefficients en 0-4.

Contribution

L'entrée sera un entier unique et peut provenir de n'importe quelle source standard (par exemple STDIN ou arguments de fonction). Vous devez prendre en charge l'entrée jusqu'au plus grand entier afin que la sortie ne déborde pas.

Production

Imprimez ou renvoyez le nombre de polynômes irréductibles sur GF (5). Notez que ces chiffres grossissent assez rapidement.

Exemples

In : Out
 1 : 5
 2 : 10
 3 : 40
 4 : 150
 5 : 624
 6 : 2580
 7 : 11160
 8 : 48750
 9 : 217000
10 : 976248
11 : 4438920

Notez que ces numéros forment la séquence A001692 dans OEIS.

Gelée , 30 23 22 20 octets

ÆF>1’PḄ
ÆDµU5*×Ç€S:Ṫ

Essayez-le en ligne! ou vérifier tous les cas de test à la fois .

Algorithme

Cela utilise la formule

à partir de la page OEIS, où d | n indique que l'on additionne sur tous les diviseurs d de n , et μ représente la fonction de Möbius .

Code

ÆF>1’PḄ       Monadic helper link. Argument: d
              This link computes the Möbius function of d.

ÆF            Factor d into prime-exponent pairs.
  >1          Compare each prime and exponent with 1. Returns 1 or 0.
    ’         Decrement each Boolean, resulting in 0 or -1.
     P        Take the product of all Booleans, for both primes and exponents.
      Ḅ       Convert from base 2 to integer. This is a sneaky way to map [0, b] to
              b and [] to 0.

ÆDµU5*×Ç€S:Ṫ  Main link. Input: n

ÆD            Compute all divisors of n.
  µ           Begin a new, monadic chain. Argument: divisors of n
   U          Reverse the divisors, effectively computing n/d for each divisor d.
              Compute 5 ** (n/d) for each n/d.

       ǀ     Map the helper link over the (ascending) divisors.
      ×       Multiply the powers by the results from Ç.
         S    Add the resulting products.
          Ṫ   Divide the sum by the last divisor (n).

Mathematica, 39 38 octets

DivisorSum[a=#,5^(a/#)MoebiusMu@#/a&]&

Utilise la même formule que la réponse Jelly.

Pari / GP , 17 octets

n->ffnbirred(5,n)

Essayez-le en ligne!

Pari / GP , sans intégré, 35 octets

n->sumdiv(n,d,5^(n/d)*moebius(d)/n)

Essayez-le en ligne!