Ein Polynom mit Koeffizienten in einem Feld F heißt irreduzibel gegenüber F, wenn es nicht in das Produkt von Polynomen niedrigeren Grades mit Koeffizienten in F zerlegt werden kann .
Betrachten Sie Polynome über dem Galoisfeld GF (5). Dieses Feld enthält 5 Elemente, nämlich die Nummern 0, 1, 2, 3 und 4.
Aufgabe
Berechnen Sie bei einer positiven ganzen Zahl n die Anzahl der irreduziblen Polynome des Grades n über GF (5). Dies sind einfach die Polynome mit Koeffizienten in 0-4, die nicht in andere Polynome mit Koeffizienten in 0-4 zerlegt werden können.
Eingang
Die Eingabe ist eine einzelne Ganzzahl und kann aus einer beliebigen Standardquelle stammen (z. B. STDIN- oder Funktionsargumente). Sie müssen die Eingabe bis zur größten Ganzzahl unterstützen, damit die Ausgabe nicht überläuft.
Ausgabe
Anzahl der Polynome drucken oder zurückgeben, die über GF nicht reduzierbar sind (5). Beachten Sie, dass diese Zahlen ziemlich schnell groß werden.
Beispiele
In : Out
1 : 5
2 : 10
3 : 40
4 : 150
5 : 624
6 : 2580
7 : 11160
8 : 48750
9 : 217000
10 : 976248
11 : 4438920
Beachten Sie, dass diese Nummern die Sequenz A001692 in OEIS bilden.
quelle
Antworten:
Jelly ,
30232220 BytesProbieren Sie es online! oder überprüfen Sie alle Testfälle auf einmal .
Algorithmus
Dies verwendet die Formel
von der OEIS-Seite, wo d | n gibt an, dass wir über alle Teiler d von n summieren und μ die Möbius-Funktion darstellt .
Code
quelle
Mathematica,
3938 BytesVerwendet die gleiche Formel wie die Gelee-Antwort.
quelle
DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]&
Pari / GP , 17 Bytes
Probieren Sie es online!
Pari / GP , ohne eingebautes, 35 Bytes
Probieren Sie es online!
quelle