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


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


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.

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

5 Answers 5


Jelly, 30 23 22 20 bytes


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


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.


Æ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).
  • 1
    \$\begingroup\$ I love these Jelly answers to hard math ! :) \$\endgroup\$
    – user9206
    Jan 19, 2016 at 9:20

Mathematica, 39 38 bytes


Uses the same formula as the Jelly answer.

  • \$\begingroup\$ +1 for teaching me about the named-function operator, but I think it's a byte shorter without: DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]& \$\endgroup\$ 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


Try it online!

Pari/GP, without built-in, 33 bytes


Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.