Loop adalah struktur aljabar yang cukup sederhana. Ini adalah tuple (G, +) di mana G adalah satu set dan + adalah operator biner G × G → G . Yaitu + mengambil dua elemen dari G dan mengembalikan elemen baru. Operator juga harus memenuhi dua properti
Pembatalan: Untuk setiap a dan b di G terdapat unik x dan y di G sedemikian rupa
a + x = b y + a = b
Identitas: Ada e dalam G sedemikian rupa sehingga untuk setiap a dalam G
e + a = a a + e = a
Jika Anda terbiasa dengan konsep grup, Anda mungkin memperhatikan bahwa loop hanyalah grup yang tidak memiliki properti asosiatif.
Loop sangat sederhana sehingga orang ingin menambahkan lebih banyak aturan untuk membuat struktur baru yang lebih menarik. Salah satu struktur tersebut adalah loop Moufang yang merupakan loop yang juga memenuhi empat identitas berikut untuk semua x , y dan z dalam G
z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)
Sebagai contoh, tabel Cayley berikut mewakili loop Moufang:
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
(Jika Anda tidak terbiasa tabel Cayley adalah matriks persegi M di mana M i, j sama dengan i + j . Ini adalah cara praktis untuk mewakili operator biner pada suatu set.)
Kita dapat menunjukkan bahwa ada identitas dengan mudahnya 0
. Pembatalan agak sulit untuk ditunjukkan tetapi pendekatan brute force menghasilkan tabel ini
b a → 0 1 2 3
↓
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
Di mana elemen kami adalah solusi untuk
a + x = b = x + a
(Anda mungkin memperhatikan bahwa tabel ini identik dengan tabel Cayley kami. Saya akan membiarkannya sebagai latihan bagi pembaca untuk mencari tahu mengapa ini terjadi pada loop Moufang ini)
Sekarang kita perlu memverifikasi identitas Moufang untuk struktur kita. Ada dua cara untuk melakukan ini untuk struktur tertentu cara pertama adalah untuk menyadari bahwa itu asosiatif dan dengan demikian secara otomatis memenuhi kriteria, namun ini tidak akan berfungsi secara umum sehingga kami lebih suka dengan kasar memaksakan hasilnya. Ada 3 variabel bebas masing-masing dengan potensi 4 nilai di setiap ekspresi di sini. Ini berarti kita harus melakukan perhitungan 7 * 4 3 atau 448. Saya akan meninggalkan perhitungan mentah, tetapi di sini ada beberapa Haskell yang dapat Anda gunakan untuk memverifikasi ini .
Tugas
Diberikan bilangan bulat positif n sebagai input output jumlah loop Moufang yang memiliki urutan n . (urutan grup adalah ukuran set)
Ini adalah kode-golf sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.
Uji kasus
Berikut adalah jumlah loop Moufang untuk 71 input pertama
1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1
sumber
12
tidak11
. Aku seharusnya menyadari itu karena11
bilangan prima.Jawaban:
Python 3 ,
475410 byteTerima kasih kepada Mr.Xcoder untuk menghemat beberapa byte!
Gunakan simetri rumus untuk menghemat 65 byte. Ya itu banyak.
Cobalah online!
Beberapa
and
dapat diganti dengan*
, menghasilkan bytecount yang lebih rendah tetapi dengan biaya waktu eksekusi yang jauh lebih lambat:Python 3 , ??? byte
[TODO menaruh kode di sini]
(tentu saja tidak semua
*
membuat program lebih lambat secara signifikan, hanya beberapa dari mereka yang kritis)Tidak Disatukan:
Cobalah online!
Tidak ada bilah gulir ...
Penjelasan:
Programnya cukup sederhana.
e
sedemikian rupa sehinggae
barise
'th dan kolom' th sama dengan[0, 1, 2, ..., n-1]
, yang merupakan kondisi yang sama denganJadi, bagiannya
kode memeriksa itu. (untuk semua baris dalam array
T
dan transposnyaA
, yang diurutkan sama denganrangeN
, dan ada satu baris di keduanyaT
danA
yang sama dengan dirinya sedang diurutkan)Keempat kondisi loop Moufang diperiksa secara manual.
Dalam kode,
(a + b)
direpresentasikan sebagaiT[a][b]
. (Karena representasi sebagai tabel Cayley). Gunakan perbandingan persamaan rantai Python untuk menghindari duplikasi(z + x) + (y + z)
.Namun, karena rumusnya simetris:
Jika kita mengganti operan
+
dalam rumus pertama, kita mendapatkan rumus kedua; dan jika kita mengganti operan+
pada rumus ketiga, kita mendapatkan rumus keempat denganx
dany
bertukar tempat.Perhatikan bahwa transposisi tabel Cayley setara dengan operator biner yang operasinya di-swap. (
x + y -> y + x
)Akhirnya, semua kandidat meja Cayley diambil dari
sehingga setiap baris adalah permutasi
rangeN
(yang[0, 1, 2, ..., n-1]
) dan adan
baris yang berbeda.sumber