Kalung Biner Primitif Reversibel yang Berbeda

8

Pendahuluan - Apa itu kalung?

Kalung adalah sesuatu yang membuat orang OEIS terobsesi. Tantangan OEIS memiliki seperti 5 urutan kalung.

Kalung panjang biner nadalah lingkaran dengan nmanik - manik yang bisa 0atau 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 1diulang dua kali. 0 1 0 1 1primitif.

0 1 1 0primitif karena 0 1dan 1 0tidak dianggap sebagai string yang sama. Kalung ini setara dengan 1 1 0 0karena 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

HyperNeutrino
sumber
4
Oh, aku mengerti— "primitif" berarti tidak bisa diputar sebagian untuk mendapatkan kalung aslinya, kan?
ETHproduk
@ ETHproductions ... Saya tidak pernah berpikir seperti itu. Ya, itu jelas merupakan pemahaman yang benar. Bagus!
HyperNeutrino
Mengapa 0 1 0 1primitif? Bukankah itu 0 1diulang dua kali?
Misha Lavrov
@MishaLavrov Terima kasih; Maksud saya "tidak primitif" ups. Terima kasih
HyperNeutrino
ಠ_ಠ Saya sedang mencari urutan OEIS untuk dikirim sebagai tantangan dan hal berikutnya yang saya lihat adalah ... ini ... kalung. ._.
totallyhuman

Jawaban:

6

Python 2 , 178 171 139 137 byte

lambda n:sum(1-any(i>int(b[j::-1]+b[:j:-1],2)or j*(i>=int(b[j:]+b[:j],2))for j in range(n))for i in range(2**n)for b in[bin(i+2**n)[3:]])

Cobalah online! Sunting: Disimpan 7 21 byte berkat @HalvardHummel.

Neil
sumber
157 byte
Halvard Hummel
1
@HalvardHummel Terima kasih, saya tidak tahu bagaimana cara menghasilkan semua permutasi dalam 1-liner.
Neil
5

JavaScript (ES6), 198 192 byte

Saya penasaran ingin tahu seperti apa jawaban matematika sepenuhnya nantinya. Jadi begini. Cukup lama tapi sangat cepat.

n=>(g=d=>d&&(n%d?0:(q=n/d,C=(a,b)=>b?C(b,a%b):a<2,M=n=>n%++k?k>n?(q%2+3)/4*(1<<q/2)+(R=d=>d&&(q%d?0:(P=k=>k--&&C(q/d,k)+P(k))(q/d)<<d)+R(d-1))(q)/q/2:M(n):n/k%k&&-M(n/k))(d,k=1))+g(d-1))(n)||1

Demo

Bagaimana?

Ini didasarkan pada formula berikut:

A000029(n) =
  (n % 2 + 3) / 4 * 2 ** floor(n / 2) +
  sum(φ(n / d) * 2 ** d, for d in divisors(n)) / (2 * n)

A001371(n) =
  1 if n = 0
  sum(μ(d) * A000029(n / d), for d in divisors(n)) if n > 0

Di mana φ adalah fungsi total Euler dan μ adalah fungsi Möbius .

n => (g = d =>
  // if d = 0, stop the recursion of g()
  d && (
    // if d is not a divisor of n, ignore this iteration
    n % d ? 0 :
    (
      // define q = n / d, C = function that tests whether a and b are coprime,
      // M = Möbius function (requires k to be initialized to 1)
      q = n / d,
      C = (a, b) => b ? C(b, a % b) : a < 2,
      M = n => n % ++k ? k > n || M(n) : n / k % k && -M(n / k)
    )(d, k = 1) * ( // invoke M with d
      // first part of the formula for A000029
      (q % 2 + 3) / 4 * (1 << q / 2) +
      // 2nd part of the formula for A000029
      (R = d =>
        // if d = 0, stop the recursion of R()
        d && (
          // if d is not a divisor of q, ignore this iteration
          q % d ? 0 :
          // compute phi(q / d) * 2 ** d
          (P = k => k-- && C(Q, k) + P(k))(Q = q / d) << d
        // recursive call to R()
        ) + R(d - 1)
      )(q) / q / 2 // invoke R with q, and divide the result by q * 2
    )
  // recursive call to g()
  ) + g(d - 1)
)(n) || 1

NB: Dalam versi golf saat ini, bagian ke 2 dari kode sekarang langsung tertanam di dalam M () . Tapi itu membuat kode lebih sulit dibaca.

Arnauld
sumber
4

Mathematica, 128 125 124 109 99 byte

1~Max~(L=Length)@(U=Union)[U[#,Reverse/@#]&/@MaximalBy[U@Partition[#,L@#,1,1]&/@{0,1}~Tuples~#,L]]&

Bagaimana itu bekerja

  • {0,1}~Tuples~# menemukan semua urutan biner dari panjang yang diberikan
  • U@Partition[#,L@#,1,1]&/@... menemukan semua kemungkinan rotasi masing-masing
  • MaximalBy[...,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

Misha Lavrov
sumber
1
Saya pikir jika Anda mengganti Lengthdengan Ldan menentukan L=Length;, Anda bisa menghemat byte.
Jonathan Frech
1
126 byte .
Jonathan Frech
125, karena saya lupa bermain golf salah satu contoh Panjang. Terima kasih!
Misha Lavrov
Dan sekarang sudah 124, karena saya telah belajar dari teladan Anda dan mengubah yang lain ==1menjadi a <2.
Misha Lavrov
3

Sekam , 21 byte

Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2

Cobalah online! Tautan menunjukkan hasil dari 0 hingga 10.

Penjelasan

Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2  Implicit input, say n=4.
                  Rḋ2  The list [1,0] repeated n times: [[1,0],[1,0],[1,0],[1,0]]
                 Π     Cartesian product: [[1,1,1,1],[0,1,1,1],[1,0,1,1],...,[0,0,0,0]]
       mȯ              For each list, say x=[0,1,0,0]:
              ¡ṙ1        Iterate rotation by one step: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],...
             U           Take prefix of unique values: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]
         ṁSe↔            After each element, insert its reversal: [[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1],[0,0,0,1],[1,0,0,0],[0,0,1,0],[0,1,0,0]]
     üO                Remove duplicates with respect to sorting.
   mL                  Get length of each list of lists.
Ṡ#▲                    Count the number of maximal lengths.
Zgarb
sumber
2

Jelly , 25 byte

2ḶṗµṙJ;U$ṢḢµ€QµsJṖE€ẸṆµ€S

Cobalah online!

Sangat tidak efisien.

Erik the Outgolfer
sumber
1

Javascript (ES7), 180 byte

n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length

Penjelasan:

n=>[...Array(2**n)].filter((_,m)=>(     // For every number m from 0 to 2^n-1
    m=m.toString(2).padStart(n,0),      // Take the binary representation (padded)

    ![...m].some(_=>(                   // Repeat once for every digit in m
        m=m.replace(/(.)(.*)/,"$2$1"),  // Rotate m one step
        s[m]|s[[...m].reverse().join``] // Search for m and the reverse of m in the
    ))                                  // lookup table

    &!/^(.+)\1+$/.test(m)               // Test if m is primitive
    &(s[m]=1)                           // Add m to the lookup table

),s=[]).length                          // Get the length of the list of numbers that
                                        // satisfy the above conditions

f=n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length
<input id=i type=number value=5/><button onclick="o.innerText=f(i.value)">Test</button><br><pre id=o></pre>

Herman L.
sumber