Pendahuluan - Apa itu kalung?
Kalung adalah sesuatu yang membuat orang OEIS terobsesi. Tantangan OEIS memiliki seperti 5 urutan kalung.
Kalung panjang biner n
adalah lingkaran dengan n
manik - manik yang bisa 0
atau 1
. Dua kalung adalah sama jika satu dapat diputar untuk menjadi yang lain, dan dua kalung yang dapat dibalik adalah sama jika satu dapat diputar, terbalik, atau terbalik dan diputar untuk menjadi yang lain.
Kalung primitif adalah kalung yang tidak dapat dinyatakan sebagai lebih dari satu salinan untaian manik-manik yang dirantai menjadi satu. Perhatikan bahwa salinan harus dikumpulkan semua dalam urutan yang sama (tidak terbalik) agar kalung dianggap non-primitif.
Sebagai contoh, mari kita lihat kalung ini: 0 1 1 0 1 1
. Itu tidak primitif karena dapat diekspresikan sebagai 0 1 1
diulang dua kali. 0 1 0 1 1
primitif.
0 1 1 0
primitif karena 0 1
dan 1 0
tidak dianggap sebagai string yang sama. Kalung ini setara dengan 1 1 0 0
karena dapat diputar satu manik untuk menjadi yang satu ini, tetapi tidak setara dengan 0 1 0 1
(yang tidak primitif dengan cara).
Tantangan
Dengan bilangan bulat non-negatif n
, kembalikan jumlah kalung biner primitif panjang reversibel yang berbeda n
. Input dan output masing-masing sebagai integer tunggal.
Beberapa istilah pertama dari urutan ini adalah 1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110
, 0-diindeks.
Ini adalah OEIS A001371
Referensi Implementasi di Python 3 - cukup lambat
sumber
0 1 0 1
primitif? Bukankah itu0 1
diulang dua kali?Jawaban:
Python 2 ,
178171139137 byteCobalah online! Sunting: Disimpan
721 byte berkat @HalvardHummel.sumber
JavaScript (ES6),
198192 byteSaya penasaran ingin tahu seperti apa jawaban matematika sepenuhnya nantinya. Jadi begini. Cukup lama tapi sangat cepat.
Demo
Tampilkan cuplikan kode
Bagaimana?
Ini didasarkan pada formula berikut:
Di mana φ adalah fungsi total Euler dan μ adalah fungsi Möbius .
NB: Dalam versi golf saat ini, bagian ke 2 dari kode sekarang langsung tertanam di dalam M () . Tapi itu membuat kode lebih sulit dibaca.
sumber
Mathematica,
12812512410999 byteBagaimana itu bekerja
{0,1}~Tuples~#
menemukan semua urutan biner dari panjang yang diberikanU@Partition[#,L@#,1,1]&/@...
menemukan semua kemungkinan rotasi masing-masingMaximalBy[...,L]
mengambil entri dengan rotasi paling berbeda; ini sesuai dengan kalung primitif.U[#,Reverse/@#]&/@...
menempatkan rotasi di setiap entri, dan pembalikannya, ke dalam urutan kanonik ...(L=Length)@(U=Union)[...]
... sehingga kami dapat menghapus duplikat kalung primitif, dan kemudian menghitung elemen yang tersisa.1~Max~...
kami memastikan hasilnya setidaknya 1 untuk mendapatkan istilah zeroth dengan benar.-2 byte terima kasih kepada Jonathan Frech, dan -2 terima kasih untuk saya belajar darinya
-15 byte lagi dari beralih ke
MaximalBy
dan perubahan terkait-10 dari beralih ke
Partition
sumber
Length
denganL
dan menentukanL=Length;
, Anda bisa menghemat byte.==1
menjadi a<2
.Sekam , 21 byte
Cobalah online! Tautan menunjukkan hasil dari 0 hingga 10.
Penjelasan
sumber
Jelly , 25 byte
Cobalah online!
Sangat tidak efisien.
sumber
Javascript (ES7), 180 byte
Penjelasan:
sumber