Deutliche reversible primitive binäre Halsketten

8

Einleitung - Was ist eine Halskette?

Eine Halskette ist etwas, von dem OEIS-Leute besessen sind. Die OEIS-Herausforderung besteht aus 5 Kettensequenzen.

Eine binäre Halskette mit einer Länge nist eine Schleife mit nPerlen, die entweder 0oder sind 1. Zwei Halsketten sind gleich, wenn eine gedreht werden kann, um die andere zu werden, und zwei umkehrbare Halsketten sind gleich, wenn eine gedreht, umgekehrt oder umgekehrt und gedreht werden kann, um die andere zu werden.

Eine primitive Halskette kann nicht als mehr als eine Kopie einer aneinander geketteten Perlenkette ausgedrückt werden. Beachten Sie, dass die Kopien alle in derselben Reihenfolge zusammengestellt werden müssen (keine Umkehrung), damit eine Halskette als nicht primitiv betrachtet wird.

Schauen wir uns zum Beispiel diese Kette an : 0 1 1 0 1 1. Es ist nicht primitiv, weil es 0 1 1zweimal wiederholt ausgedrückt werden kann . 0 1 0 1 1ist primitiv.

0 1 1 0ist primitiv, weil 0 1und 1 0nicht als die gleiche Zeichenfolge betrachtet werden. Diese Kette ist äquivalent zu, 1 1 0 0weil sie um eine Perle nach links gedreht werden kann, um diese zu werden, aber nicht äquivalent zu 0 1 0 1(was übrigens nicht primitiv ist).

Herausforderung

Geben Sie bei einer nicht negativen Ganzzahl ndie Anzahl der verschiedenen reversiblen primitiven binären Halsketten mit der Länge zurück n. Eingabe und Ausgabe jeweils als einzelne Ganzzahl.

Die ersten Begriffe dieser Sequenz sind 1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 41100-indiziert.

Dies ist OEIS A001371

Referenzimplementierung in Python 3 - ziemlich langsam

HyperNeutrino
quelle
4
Oh, ich verstehe - "primitiv" bedeutet, dass es nicht teilweise gedreht werden kann, um die ursprüngliche Halskette zu erhalten, oder?
ETHproductions
@ETHproductions ... Ich habe es nie so gesehen. Ja, das ist definitiv ein korrektes Verständnis. Nett!
HyperNeutrino
Warum ist 0 1 0 1primitiv? Wird es nicht 0 1zweimal wiederholt?
Mischa Lawrow
@ MischaLavrov Danke; Ich meinte "nicht primitiv" whoops. Vielen Dank
HyperNeutrino
ಠ_ಠ Ich habe nach einer OEIS-Sequenz gesucht, die ich als Herausforderung veröffentlichen kann, und als nächstes sehe ich ... diese ... Halsketten. ._.
totalhuman

Antworten:

6

Python 2 , 178 171 139 137 Bytes

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:]])

Probieren Sie es online aus! Bearbeiten: 7 21 Bytes dank @HalvardHummel gespeichert.

Neil
quelle
157 Bytes
Halvard Hummel
1
@HalvardHummel Danke, ich konnte nicht herausfinden, wie alle Permutationen in einem 1-Liner generiert werden können.
Neil
5

JavaScript (ES6), 198 192 Bytes

Ich war neugierig zu wissen, wie eine vollständig mathematische Antwort aussehen würde. Hier ist es also. Ziemlich lang, aber sehr schnell.

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

Wie?

Dies basiert auf folgenden Formeln:

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

Wo φ ist Eulersche Phi-Funktion und μ ist Möbius - Funktion .

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: In der aktuellen Golfversion ist der 2. Teil des Codes jetzt direkt in M () eingebettet . Dadurch ist der Code jedoch schwerer zu lesen.

Arnauld
quelle
4

Mathematica, 128 125 124 109 99 Bytes

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

Wie es funktioniert

  • {0,1}~Tuples~# findet alle binären Sequenzen der angegebenen Länge
  • U@Partition[#,L@#,1,1]&/@... findet alle möglichen Rotationen von jedem von ihnen
  • MaximalBy[...,L]wählt die Einträge mit den deutlichsten Rotationen aus; diese entsprechen den primitiven Halsketten.
  • U[#,Reverse/@#]&/@... bringt die Rotationen in jedem Eintrag und ihre Umkehrungen in eine kanonische Reihenfolge ...
  • (L=Length)@(U=Union)[...] ... damit wir doppelte primitive Halsketten löschen und dann die verbleibenden Elemente zählen können.
  • 1~Max~... Wir stellen sicher, dass das Ergebnis mindestens 1 ist, um den nullten Term richtig zu machen.

-2 Bytes danke an Jonathan Frech und -2 danke, dass ich von ihm gelernt habe

-15 weitere Bytes vom Umschalten auf MaximalBy und damit verbundene Änderungen

-10 vom Umschalten auf Partition

Mischa Lawrow
quelle
1
Ich denke , wenn Sie ersetzen Lengthmit Lund definieren L=Length;Sie ein Byte speichern kann.
Jonathan Frech
1
126 Bytes .
Jonathan Frech
125, da ich vergessen habe, eine der Instanzen von Länge zu spielen. Vielen Dank!
Mischa Lawrow
Und jetzt ist es 124, da ich aus Ihrem Beispiel gelernt und aus einem anderen ==1ein gemacht habe <2.
Mischa Lawrow
3

Husk , 21 Bytes

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

Probieren Sie es online aus! Der Link zeigt Ergebnisse von 0 bis 10.

Erläuterung

Ṡ#▲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
quelle
1

Javascript (ES7), 180 Bytes

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

Erläuterung:

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.
quelle