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.
źródło
Odpowiedzi:
Galaretka ,
30232220 bajtówWypró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
źródło
Mathematica,
3938 bajtówUżywa tej samej formuły, co odpowiedź Jelly.
źródło
DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]&
Pari / GP , 17 bajtów
Wypróbuj online!
Pari / GP , bez wbudowanego, 35 bajtów
Wypróbuj online!
źródło