# Irreducible polynomials over GF(5)

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.

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.

• PARI/GP 46 bytes on A001692 ;) Is there a time limit? Jan 18, 2016 at 4:39
• @Bruce_Forte Nope. Jan 18, 2016 at 4:42

# Jelly, 302322 20 bytes

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


### 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            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 Ç.
:Ṫ  Divide the sum by the last divisor (n).

• I love these Jelly answers to hard math ! :)
– user9206
Jan 19, 2016 at 9:20

# Mathematica, 39 38 bytes

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


Uses the same formula as the Jelly answer.

• +1 for teaching me about the named-function operator, but I think it's a byte shorter without: DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]& Jan 19, 2016 at 21:30

# 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.

# 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}


# 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!