Latar Belakang
Terakhir kali, kami menghitung kelompok dengan ukuran tertentu , yang merupakan masalah non-sepele.
Kali ini, kami hanya akan menghitung grup Abelian , yaitu grup dengan operasi komutatif. Secara formal, kelompok (G, *) adalah Abelian jika x * y = y * x untuk semua x, y di G .
Masalahnya menjadi lebih sederhana dengan cara ini, jadi kita akan menghitungnya secara efisien.
Tugas
Tulis program atau fungsi yang menerima bilangan bulat non-negatif n sebagai input dan mencetak atau mengembalikan jumlah kelompok Abelian non-isomorfik orde n .
Salah satu cara menghitung jumlah grup - yang akan kami tunjukkan dengan A (n) - adalah dengan mengamati yang berikut:
A (0) = 0
Jika p adalah bilangan prima, A (p k ) sama dengan jumlah partisi integer k . ( cfr . OEIS A000041 )
Jika n = mk , dan m dan k adalah co-prime, A (n) = A (m) A (k) .
Anda dapat menggunakan ini atau metode penghitungan A (n) lainnya .
Uji kasus
Input Output
0 0
1 1
2 1
3 1
4 2
5 1
6 1
7 1
8 3
9 2
10 1
11 1
12 2
13 1
14 1
15 1
16 5
17 1
18 2
19 1
20 2
4611686018427387904 1300156
5587736968198167552 155232
9223371994482243049 2
(diambil dari OEIS A000688 )
Aturan tambahan
Diberi cukup waktu, RAM dan ukuran register yang dapat menampung input, kode Anda harus bekerja (secara teori) untuk bilangan bulat besar yang sewenang-wenang.
Kode Anda harus bekerja untuk semua bilangan bulat antara 0 dan 2 63 - 1 dan selesai di bawah 10 menit pada komputer saya (Intel i7-3770, 16 GiB RAM, Fedora 21).
Pastikan Anda menghitung waktu kode Anda untuk tiga kasus pengujian terakhir sebelum mengirimkan jawaban Anda.
Built-in yang meremehkan tugas ini, seperti Mathematica
FiniteAbelianGroupCount
, tidak diperbolehkan.Built-in yang mengembalikan atau menghitung partisi integer angka atau partisi daftar tidak diperbolehkan.
Aturan standar kode-golf berlaku.
sumber
Jawaban:
CJam (
3938 bytes)Demo online
Ini mengikuti garis yang disarankan untuk menemukan factorisation utama (
mF
) dan kemudian menghitung partisi masing-masing kekuatan dan mengambil produk mereka.Ada dua kasus khusus untuk
mF
: itu faktor0
as0^1
dan1
as1^1
. Yang terakhir tidak memerlukan perlakuan khusus: ada satu kelompok Abelian ukuran 1, dan satu partisi 1. Namun, nol memang membutuhkan kasing khusus.Penghitungan partisi menggunakan pengulangan untuk
A008284(n, k)
, jumlah partisin
menjadik
beberapa bagian. Dalam OEIS diberikan sebagaitapi saya pikir lebih bermanfaat untuk memikirkan jumlah yang berkisar dari
1
hinggamin(k, n-k)
.Pembedahan
sumber
CJam,
50494743 byteMenggunakan
mF
factorisation bawaan CJam dan port memoised dari fungsi nomor partisi Python ini:atau ungolfed:
Seperti jawaban @ RetoKoradi, kasus terakhir membutuhkan sekitar 17 detik pada penerjemah offline karena itulah berapa lama yang diperlukan CJam untuk memfaktorkan angka tersebut. Oleh karena itu saya telah meninggalkannya dari test suite online ini .
Penjelasan lengkap
sumber
Mathematica,
969488 byteSaya tidak begitu mahir dengan Mathematica, tapi saya pikir saya akan mencobanya. Terima kasih kepada @ MartinBüttner untuk -6 byte.
Ini menggunakan rumus fungsi pembangkit untuk partisi integer.
sumber
CJam, 58 byte
Cobalah online
Contoh pengujian terakhir membutuhkan waktu lama (atau setidaknya lebih lama dari yang saya mau tunggu) di penerjemah online, tetapi selesai dalam 17 detik dengan versi offline CJam di laptop saya. Semua contoh uji lainnya cukup instan.
Ini menggunakan
mF
operator CJam , yang memberikan faktorisasi utama dengan eksponen. Hasilnya kemudian produk dari partisi dihitung untuk setiap eksponen.Bagian utama dari kode adalah menghitung jumlah partisi. Saya menerapkan algoritma rekursif pada halaman wikipedia , menggunakan
j
operator yang mendukung rekursi dengan memoisasi.Penjelasan:
sumber