Wenn wir eine Fibonacci-ähnliche Folge als f k (n) = (f k (n-1) + f k (n-2))% k definieren , ist die Folge für eine ganze Zahl k (wobei % der Modulo-Operator ist) wird notwendigerweise zyklisch sein, weil es nur k 2 verschiedene Werte für (f k (n-1), f k (n-2)) gibt . Da dieser Zyklus in der Regel nicht alle möglichen Wertepaare enthält, kann es in Abhängigkeit von den beiden Startwerten f k (0) und f k (1) zu unterschiedlichen Zyklen kommen. Zum Beispiel für k = 2Abhängig von den ersten beiden Werten haben wir die folgenden vier Möglichkeiten:
0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 0, 1, 1, 0, 1, 1, ...
1, 0, 1, 1, 0, 1, 1, 0, 1, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, ...
Aufgrund der zyklischen Natur der Sequenzen gibt es hier eigentlich nur zwei grundlegend unterschiedliche Sequenzen mit den Umlaufbahnen (0) und (0, 1, 1) . Schauen wir uns k = 3 an :
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, ...
0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, ...
1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, ...
1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...
1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, ...
2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...
2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, ...
2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, ...
Auch hier gibt es nur zwei verschiedene Umlaufbahnen: (0) und (0, 1, 1, 2, 0, 2, 2, 1) .
Für höhere k erhalten wir möglicherweise mehr Umlaufbahnen, aber sie fallen immer noch in eine vergleichsweise kleine Anzahl von Klassen. Zum Beispiel ergibt k = 4 die vier Bahnen (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) und k = 5 die drei Bahnen (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) und (1, 3, 4, 2) .
Ihre Aufgabe bei dieser Herausforderung ist es, zu berechnen, wie viele Umlaufbahnen die Sequenz für ein gegebenes k erzeugt . Dies ist OEIS A015134 . Hier sind die ersten 100 Werte (ab k = 1 ):
1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16,
29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19,
86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, 25, 26, 42, 40, 27, 52,
160, 74, 63, 126, 62, 70, 63, 134, 104, 64, 57, 78, 34, 132, 101, 60,
74, 222, 37, 38, 62, 328, 89, 64, 82, 124, 41, 86, 42, 172, 75, 44,
184, 178, 181, 132, 82, 180, 99, 140, 104, 246, 49, 50, 114, 76
Stellen Sie sicher, dass k = 11 ist. Dies ist die erste Eingabe, die mehr als k Umlaufbahnen liefert .
Regeln
Sie erhalten eine positive Ganzzahl k und sollten A015134 (k) ausgeben .
Sie können ein Programm oder eine Funktion schreiben und eine der Standardmethoden zum Empfangen von Eingaben und zum Bereitstellen von Ausgaben verwenden.
Sie können jede Programmiersprache verwenden , aber beachten Sie, dass diese Lücken standardmäßig verboten sind.
Das ist Code-Golf , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .
quelle
Antworten:
Schale ,
1716 BytesProbieren Sie es online!
Erläuterung
quelle
Bash,
172,119,113, 91 BytesProbieren Sie es online aus
quelle
Wolfram Language (Mathematica) ,
76-70BytesProbieren Sie es online!
Wie es funktioniert
Wir konstruieren den Graphen nach den Regeln
{{0,0}->{0,0}, {1,0}->{1,1}, ...}
, die bei zwei Elementen einer verallgemeinerten Fibonacci-Folge das nächste Modulo findenn
. DasEdgeCycleMatrix
gibt die Inzidenzmatrix von Zyklen zu Kanten in diesem Diagramm an; Wir wollen seine Zeilen zählen.(Es gibt eine Reihe von integrierten Funktionen, die ähnliche Aufgaben ausführen, jedoch
ConnectedComponents
länger sind undFindCycle
viele zusätzliche Eingaben benötigen, damit sie funktionieren. AußerdemEdgeCycleMatrix
handelt es sich um ein rechteckiges Array, das nicht wie die anderen beiden Formen witzig ist . Dies hilft später. )Um die Zeilen der Matrix zu zählen, nehmen wir die Fakultät der Einträge, um sie in eine Matrix aller zu verwandeln, und nehmen dann den Trace. (Jeder Zyklus enthält mindestens eine Kante, und daher gibt es mindestens so viele Spalten wie Zeilen. Dies zählt also die Zeilen und nicht die Spalten.)
quelle
MATL ,
3836 BytesProbieren Sie es online! Bei Eingabeüberschreitung tritt im Online-Compiler eine Zeitüberschreitung auf
7
.Erläuterung
Der Code definiert Umlaufbahnen in Form komplexer Zahlen, wobei der Imaginärteil der neue Term und der Realteil der vorangehende Term in der Fibonacci-Sequenz ist. Jeder komplexe Wert codiert den Status der Sequenz. Bei gegebenem
a+jb
nächsten Wert wird nämlich berechnet alsb+j(a+b)
.Die möglichen Startwerte sind
a+jb
mita
,b
in[0, 1, ..., k-1]
. Für jeden Startwert iteriert der Code einigek^2
Male. Um den Code zu verkürzen, wird jede Iteration auf alle angewendet akkumulierten Werte , und die Ergebnisse werden dedupliziert (was ohnehin am Ende erforderlich wäre). Nach der letzten Iteration wird der Vektor der deduplizierten komplexen Werte sortiert (nach Absolutwert, dann nach Winkel). Dies gibt eine "Signatur" für jede Umlaufbahn.Am Ende des Programms werden die Signaturen in einem Zellenarray gesammelt. Die Anzahl der eindeutigen Signaturen ist die gewünschte Ausgabe.
quelle
Haskell ,
196.191BytesProbieren Sie es online!
Dies könnte wahrscheinlich verbessert werden. Insbesondere, wenn jemand einen Weg findet
isInfixOf
, den Import zu vermeiden und zu entfernen.Grundlegende Idee ist es, eine Liste von "Zuständen" (Tupel, die die beiden vorherigen Werte enthalten) zu erstellen, um zu sehen, wann der Zyklus beginnt. Dann prüfen wir, ob sich jeder Orbit von seinen Vorgängern unterscheidet (funktioniert genau umgekehrt, ist aber schwer in Worte zu fassen). Um zu überprüfen, ob die Umlaufbahnen gleich sind, prüfen wir, ob die Länge gleich ist und ob eine in die andere passt, die mit sich selbst verkettet ist. Zum Beispiel
[0,2,2]
,[2,2,0]
: Länge beider ist 3 und[0,2,2,0,2,2]
enthält[2,2,0]
als kontinuierliche Subsequenz. Ich bin nicht sicher, ob es narrensicher ist, aber es scheint zu funktionieren.EDIT: Danke an Laikoni für die 5 Bytes! Ich hätte mehr von diesen Tipps lesen sollen.
quelle
length
. Ein weiteres Byte kann mit gespeichert!
werden|r<-p++[a]=r!b
.JavaScript (ES6),
337-335ByteEntschuldigen Sie den Brute-Force-Algorithmus Ω (k ^ 3).
Die Leistung ...
Als ich A015134 berechnet habe (etwas jenseits von k = 50), hat es das 60s-Limit für TIO überschritten.Erklärung (Ungolfed)
quelle
Perl 5, 80 + 1 (-p) Bytes
Probieren Sie es online aus
quelle
Gelee , 17 Bytes
Probieren Sie es online!
quelle
JavaScript (ES6), 102 Byte
Gibt eine Funktion zurück, die das Ergebnis liefert. Für 3 weitere Bytes können wir das Ergebnis direkt zurückgeben lassen:
Beide haben Zeitkomplexität O (n 2 ).
quelle
Python 2 , 214 Bytes
Probieren Sie es online!
Es ist nicht sehr effizient, aber es ist das Golfspiel, das ich machen kann.
quelle