Irreducible polynomials over GF(5)

Question

A polynomial with coefficients in some field F is called irreducible over F if it cannot be decomposed into the product of lower degree polynomials with coefficients in F.

Consider polynomials over the Galois field GF(5). This field contains 5 elements, namely the numbers 0, 1, 2, 3, and 4.

Task

Given a positive integer n, compute the number of irreducible polynomials of degree n over GF(5). These are simply the polynomials with coefficients in 0-4 which cannot be factored into other polynomials with coefficients in 0-4.

Input

Input will be a single integer and can come from any standard source (e.g. STDIN or function arguments). You must support input up to the largest integer such that the output does not overflow.

Output

Print or return the number of polynomials that are irreducible over GF(5). Note that these numbers get large rather quickly.

Examples

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

Note that these numbers form the sequence A001692 in OEIS.

Answer 1

Jelly, 30 23 22 20 bytes

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

Try it online! or verify all test cases at once.

Algorithm

This uses the formula

$$\text{A001692}(n) = \frac 1 n \sum_{d|n} \mu(d)5^\frac n d$$

from the OEIS page, where \$d | n\$ indicates that we sum over all divisors \$d\$ of \$n\$, and \$\mu\$ represents the Möbius function.

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.
    5*        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).

Answer 2

Mathematica, 39 38 bytes

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

Uses the same formula as the Jelly answer.

Answer 3

Python 3, 59 bytes

f=lambda n:(5**n-sum(d*f(d)for d in range(1,n)if n%d<1))//n

Try it online!

This uses the formula

$$f(n) = \frac 1 n \sum_{d|n} \mu(d)5^\frac n d$$

but applies Möbius inversion to turn it into

$$5^n = \sum_{d|n} f(d) d$$

and solves for \$f(n)\$.

55 bytes

f=lambda n,d=1:d//n*5**n/n or f(n,d+1)-d*f(d)*(n%d<1)/n

Try it online!

Has float precision issues for larger inputs.

Answer 4

Scala, 74 bytes

Port of @xnor's Python answer in Scala.

Use the formula: \$5^n = \sum\limits_{d|n} f(d) d\$

Try it online!

n=>{(BigInt(5).pow(n)-(1 until n).filter(d=>n%d==0).map(d=>d*f(d)).sum)/n}

Answer 5

Pari/GP, 17 bytes

n->ffnbirred(5,n)

Try it online!

---

Pari/GP, without built-in, 33 bytes

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

Try it online!