Wielomian ze współczynnikami w pewnym polu F nazywa się nierozkładalny przez F , jeśli nie może być rozłożona do produktu niższych wielomianów stopnia, ze współczynnikami w F .

Rozważ wielomiany nad polem Galois GF (5). To pole zawiera 5 elementów, a mianowicie liczby 0, 1, 2, 3 i 4.

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą n , oblicz liczbę nieredukowalnych wielomianów stopnia n nad GF (5). Są to po prostu wielomiany o współczynnikach w 0-4, których nie można rozłożyć na inne wielomiany o współczynnikach w 0-4.

Wejście

Dane wejściowe będą jedną liczbą całkowitą i mogą pochodzić z dowolnego standardowego źródła (np. STDIN lub argumenty funkcji). Musisz obsługiwać dane wejściowe do największej liczby całkowitej, aby dane wyjściowe się nie przepełniły.

Wynik

Wydrukuj lub zwróć liczbę wielomianów, które są nieredukowalne w stosunku do GF (5). Zauważ, że liczby te stają się dość duże dość szybko.

Przykłady

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

Należy zauważyć, że liczby te tworzą sekwencję A001692 w OEIS.

Galaretka , 30 23 22 20 bajtów

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

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Algorytm

To używa formuły

ze strony OEIS, gdzie d | n oznacza, że ​​sumujemy wszystkie dzielniki d od n , a μ reprezentuje funkcję Möbiusa .

Kod

Æ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 bajtów

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

Używa tej samej formuły, co odpowiedź Jelly.

Pari / GP , 17 bajtów

n->ffnbirred(5,n)

Wypróbuj online!

Pari / GP , bez wbudowanego, 35 bajtów

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

Wypróbuj online!