Sebuah polinomial dengan koefisien di beberapa bidang F disebut tereduksi lebih F jika tidak dapat didekomposisi menjadi produk dari polinomial derajat lebih rendah dengan koefisien di F .
Pertimbangkan polinomial di bidang Galois GF (5). Bidang ini berisi 5 elemen, yaitu angka 0, 1, 2, 3, dan 4.
Tugas
Dengan bilangan bulat positif n , hitung jumlah polinomial tak tereduksi derajat n di atas GF (5). Ini hanyalah polinomial dengan koefisien pada 0-4 yang tidak dapat difaktorkan ke dalam polinomial lain dengan koefisien pada 0-4.
Memasukkan
Input akan berupa bilangan bulat tunggal dan dapat berasal dari sumber standar apa pun (mis., STDIN atau argumen fungsi). Anda harus mendukung input hingga bilangan bulat terbesar sehingga output tidak meluap.
Keluaran
Cetak atau kembalikan jumlah polinomial yang tidak dapat direduksi lebih dari GF (5). Perhatikan bahwa angka-angka ini menjadi besar agak cepat.
Contohnya
In : Out
1 : 5
2 : 10
3 : 40
4 : 150
5 : 624
6 : 2580
7 : 11160
8 : 48750
9 : 217000
10 : 976248
11 : 4438920
Perhatikan bahwa angka-angka ini membentuk urutan A001692 di OEIS.
sumber
Jawaban:
Jelly ,
30232220 byteCobalah online! atau verifikasi semua kasus uji sekaligus .
Algoritma
Ini menggunakan rumus
dari halaman OEIS, di mana d | n menunjukkan bahwa kita menjumlahkan semua pembagi d dari n , dan μ mewakili fungsi Möbius .
Kode
sumber
Mathematica,
3938 byteMenggunakan rumus yang sama dengan jawaban Jelly.
sumber
DivisorSum[n=#,5^(n/#)MoebiusMu@#/n&]&
Pari / GP , 17 byte
Cobalah online!
Pari / GP , tanpa built-in, 35 byte
Cobalah online!
sumber