Полином с коэффициентами в некотором поле F называется неприводимым над F , если она не может быть разложена в произведение многочленов низших степеней с коэффициентами из F .

Рассмотрим многочлены над полем Галуа GF (5). Это поле содержит 5 элементов, а именно числа 0, 1, 2, 3 и 4.

задача

Учитывая положительное целое число n , вычислите число неприводимых многочленов степени n над GF (5). Это просто многочлены с коэффициентами в 0-4, которые нельзя разложить на другие многочлены с коэффициентами в 0-4.

вход

Ввод будет одним целым числом и может происходить из любого стандартного источника (например, STDIN или аргументы функции). Вы должны поддерживать ввод до наибольшего целого числа, чтобы вывод не переполнялся.

Выход

Выведите или верните число неприводимых по GF полиномов (5). Обратите внимание, что эти цифры становятся большими довольно быстро.

Примеры

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

Обратите внимание, что эти числа образуют последовательность A001692 в OEIS.

Желе , 30 23 22 20 байт

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

Попробуйте онлайн! или проверьте все тестовые случаи одновременно .

Алгоритм

Это использует формулу

со страницы OEIS, где d | n указывает, что мы суммируем по всем делителям d из n , а µ представляет функцию Мёбиуса .

Код

Æ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 байт

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

Использует ту же формулу, что и ответ желе.

Пари / ГП , 17 байт

n->ffnbirred(5,n)

Попробуйте онлайн!

Пари / ГП , без встроенного, 35 байт

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

Попробуйте онлайн!