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 n
ist eine Schleife mit n
Perlen, die entweder 0
oder 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 1
zweimal wiederholt ausgedrückt werden kann . 0 1 0 1 1
ist primitiv.
0 1 1 0
ist primitiv, weil 0 1
und 1 0
nicht als die gleiche Zeichenfolge betrachtet werden. Diese Kette ist äquivalent zu, 1 1 0 0
weil 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 n
die 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, 4110
0-indiziert.
Dies ist OEIS A001371
Referenzimplementierung in Python 3 - ziemlich langsam
quelle
0 1 0 1
primitiv? Wird es nicht0 1
zweimal wiederholt?Antworten:
Python 2 ,
178171139137 BytesProbieren Sie es online aus! Bearbeiten:
721 Bytes dank @HalvardHummel gespeichert.quelle
JavaScript (ES6),
198192 BytesIch war neugierig zu wissen, wie eine vollständig mathematische Antwort aussehen würde. Hier ist es also. Ziemlich lang, aber sehr schnell.
Demo
Code-Snippet anzeigen
Wie?
Dies basiert auf folgenden Formeln:
Wo φ ist Eulersche Phi-Funktion und μ ist Möbius - Funktion .
NB: In der aktuellen Golfversion ist der 2. Teil des Codes jetzt direkt in M () eingebettet . Dadurch ist der Code jedoch schwerer zu lesen.
quelle
Mathematica,
12812512410999 BytesWie es funktioniert
{0,1}~Tuples~#
findet alle binären Sequenzen der angegebenen LängeU@Partition[#,L@#,1,1]&/@...
findet alle möglichen Rotationen von jedem von ihnenMaximalBy[...,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
quelle
Length
mitL
und definierenL=Length;
Sie ein Byte speichern kann.==1
ein gemacht habe<2
.Husk , 21 Bytes
Probieren Sie es online aus! Der Link zeigt Ergebnisse von 0 bis 10.
Erläuterung
quelle
Gelee , 25 Bytes
Probieren Sie es online aus!
Sehr ineffizient.
quelle
Javascript (ES7), 180 Bytes
Erläuterung:
quelle