13
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ PARI/GP 46 bytes on A001692 ;) Is there a time limit? \$\endgroup\$ – ბიმო Jan 18 '16 at 4:39
  • \$\begingroup\$ @Bruce_Forte Nope. \$\endgroup\$ – Alex A. Jan 18 '16 at 4:42
9
\$\begingroup\$

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

Mathematica, 39 38 bytes

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

Uses the same formula as the Jelly answer.

\$\endgroup\$
1
  • \$\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\$ – Martin Ender Jan 19 '16 at 21:30
1
\$\begingroup\$

Pari/GP, 17 bytes

n->ffnbirred(5,n)

Try it online!


Pari/GP, without built-in, 35 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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