Inspiriert von dieser Math.SE-Frage .
Hintergrund
Die Fibonacci-Sequenz (genannt F
) ist die Sequenz, die so beginnt 0, 1
, dass jede Zahl ( F(n)
) (nach den ersten beiden) die Summe der beiden davor ( F(n) = F(n-1) + F(n-2)
) ist.
Eine Fibonacci-Folge mod K (genannt M
) ist die Folge der Fibonacci-Zahlen mod K ( M(n) = F(n) % K
).
Es kann gezeigt werden, dass die Fibonacci-Sequenz mod K für alle K zyklisch ist, da jeder Wert durch das vorherige Paar bestimmt wird und es nur K 2 mögliche Paare von nicht negativen ganzen Zahlen gibt, die beide kleiner als K sind. Wegen der Fibonacci-Sequenz mod K ist nach dem ersten wiederholten Begriffspaar zyklisch. Eine Zahl, die im Fibonacci Sequence Mod K nicht vor dem ersten wiederholten Begriffspaar erscheint, wird niemals angezeigt.
Für K = 4
0 1 1 2 3 1 0 1 ...
Für K = 8
0 1 1 2 3 5 0 5 5 2 7 1 0 1 ...
Beachten Sie, dass für K = 8 4 und 6 nicht vor der Wiederholung erscheinen 0 1
, so dass 4 und 6 niemals in der Fibonacci-Sequenz Mod 8 erscheinen.
Herausforderung
Bei einer Ganzzahl K, die streng größer als 0 ist, werden alle nicht negativen Ganzzahlen kleiner als K ausgegeben, die nicht in der Fibonacci-Sequenz-Modifikation K enthalten sind.
Regeln
Sie können davon ausgehen, dass K in Ihren systemeigenen Integer-Typ passt ( innerhalb des vorgegebenen Rahmens ).
Wenn es nicht-negative Zahlen unter K gibt, die im Fibonacci Sequence Mod K nicht vorkommen, sollte Ihr Programm / Ihre Funktion alle diese Zahlen in angemessener Weise ausgeben.
Wenn es keine nicht-negativen ganzen Zahlen unter K gibt, die nicht in der Fibonacci-Sequenz-Modifikation K vorkommen, gibt Ihr Programm / Ihre Funktion dies möglicherweise an, indem Sie eine leere Liste zurückgeben, nichts drucken, einen Fehler erzeugen usw.
Bestellung spielt keine Rolle.
Das ist Code-Golf , also gewinnt die kürzeste Antwort in jeder Sprache.
Testfälle
Nicht leere Testfälle
8 [4, 6]
11 [4, 6, 7, 9]
12 [6]
13 [4, 6, 7, 9]
16 [4, 6, 10, 12, 14]
17 [6, 7, 10, 11]
18 [4, 6, 7, 9, 11, 12, 14]
19 [4, 6, 7, 9, 10, 12, 14]
21 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 19]
22 [4, 6, 7, 9, 15, 17, 18, 20]
23 [4, 7, 16, 19]
24 [4, 6, 9, 11, 12, 14, 15, 18, 19, 20, 22]
26 [4, 6, 7, 9, 17, 19, 20, 22]
28 [10, 12, 14, 16, 18, 19, 23]
29 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27]
31 [4, 6, 9, 12, 14, 15, 17, 18, 19, 22, 25, 29]
32 [4, 6, 10, 12, 14, 18, 20, 22, 26, 28, 30]
33 [4, 6, 7, 9, 15, 17, 18, 20, 24, 26, 27, 28, 29, 31]
34 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 30]
36 [4, 6, 7, 9, 10, 11, 12, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]
37 [9, 10, 14, 17, 20, 23, 27, 28]
38 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 36]
39 [4, 6, 7, 9, 15, 17, 19, 20, 22, 24, 30, 32, 33, 35]
...
200 [4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94, 100, 102, 108, 110, 116, 118, 124, 126, 132, 134, 140, 142, 148, 150, 156, 158, 164, 166, 172, 174, 180, 182, 188, 190, 196, 198]
...
300 [6, 18, 30, 42, 54, 66, 78, 90, 102, 114, 126, 138, 150, 162, 174, 186, 198, 210, 222, 234, 246, 258, 270, 282, 294]
...
400 [4, 6, 10, 12, 14, 20, 22, 26, 28, 30, 36, 38, 42, 44, 46, 52, 54, 58, 60, 62, 68, 70, 74, 76, 78, 84, 86, 90, 92, 94, 100, 102, 106, 108, 110, 116, 118, 122, 124, 126, 132, 134, 138, 140, 142, 148, 150, 154, 156, 158, 164, 166, 170, 172, 174, 180, 182, 186, 188, 190, 196, 198, 202, 204, 206, 212, 214, 218, 220, 222, 228, 230, 234, 236, 238, 244, 246, 250, 252, 254, 260, 262, 266, 268, 270, 276, 278, 282, 284, 286, 292, 294, 298, 300, 302, 308, 310, 314, 316, 318, 324, 326, 330, 332, 334, 340, 342, 346, 348, 350, 356, 358, 362, 364, 366, 372, 374, 378, 380, 382, 388, 390, 394, 396, 398]
...
Leere Testfälle (keine Ausgabe, Fehler, leere Liste usw. ist akzeptable Ausgabe)
1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35 ... 100 ...
Antworten:
Gelee ,
98 BytesProbieren Sie es online!
Basierend auf der Pisano-Zeit
p(n) <= 6n
von A001175 . Auchp(n) <= 6n <= n^2
fürn >= 6
undp(n) <= n^2
fürn < 6
. Dieses Byte wurde dank Dennis gespeichert.quelle
²
sollte funktionieren statt×6
.Haskell , 70 Bytes
Dank Esolanging Fruit konnten einige Bytes eingespart werden
8 Bytes dank Laikoni gespart
Probieren Sie es online!
quelle
read$show
funktioniertfromInteger
in diesem Fall nicht und spart zwei Bytes.zip[1..x^2]
zum Abschneiden, um weitere Bytes zu sparen: Probieren Sie es online aus!Perl 6 ,
43 42 3932 BytesProbier es aus
Probier es aus
Probier es aus
Probier es aus
Erweitert:
quelle
> <> 48 Bytes
Probieren Sie es online!
Übernimmt die Eingabe über das Flag -v.
Druckt viele überschüssige Zeilenumbrüche, erledigt aber die Arbeit. Dabei wird im Grunde genommen die erste Zeile verwendet, um den Satz von Zahlen zu speichern, die bisher in der Sequenz aufgetreten sind.
Wie es funktioniert:
quelle
Python 2 , 69 Bytes
Probieren Sie es online!
quelle
MATL ,
1918 BytesProbieren Sie es online!
-1 Byte danke an Guiseppe.
quelle
X~
!Python 3 , 91 Bytes
Probieren Sie es online!
quelle
Husk ,
13 1210 BytesDanke @Zgarb für -2 Bytes!
Druckt eine leere Liste, falls alle ganzen Zahlen erscheinen, Probieren Sie es online aus!
Erläuterung
quelle
U2
Sie das längste Präfix abrufen, bei dem sich kein benachbartes Paar wiederholt.Python 3 , 78 Bytes
Probieren Sie es online!
Druckt einen Satz, sodass die Ausgabe für leere Testfälle
set()
der leere Satz ist.quelle
R
9286 BytesVielen Dank an @ Giuseppe für das Speichern von 6 Bytes!
Probieren Sie es online!
Ziemlich unkomplizierte Implementierung ( vorherige Version , aber dasselbe Konzept):
quelle
setdiff
, gute Idee!1:k^2
Ansatz portieren, den alle anderen verwendenPython 3,
173152143131 BytesBesonderer Dank geht an @ovs.
Probieren Sie es online
Wie funktioniert es?
Die erste Funktion akzeptiert zwei Parameter m und n und gibt die n-te Fibonacci-Zahl mod m zurück. Die zweite Funktion durchläuft die Fibonacci-Zahlen mod k und prüft, ob 0 und 1 wiederholt werden. Es speichert die Zahlen in einer Liste und vergleicht sie mit einer Liste, die die Zahlen 1-n enthält. Die doppelten Nummern werden entfernt und die verbleibenden Nummern werden zurückgegeben.
quelle
set()
und verketteten Vergleichen.05AB1E , 10 Bytes
Probieren Sie es online!
-3 Bytes dank Emigna.
quelle
Ruby , 47 Bytes
Probieren Sie es online!
Obwohl es einige der gleichen Logik verwendet, basiert dies nicht auf GBs Antwort .
Erläuterung:
quelle
Common Lisp, 106 Bytes
Probieren Sie es online!
quelle
Pari / GP , 55 Bytes
Probieren Sie es online!
quelle
Elixier ,
148144 BytesProbieren Sie es online!
Keine besonders konkurrenzfähige Antwort, aber es hat wirklich Spaß gemacht, Golf zu spielen! Elixier ist eine ziemlich lesbare Sprache, aber eine Erklärung für das Durcheinander der Charaktere in der Mitte folgt.
Diese Erklärung besteht aus zwei Abschnitten, dem Mod-Fibonacci und der Funktionsweise
Mod-fib:
Dies gibt einen unendlichen Strom von Fibonacci-Mod zurück
x
. Es beginnt mit einem Akkumulator{1,1}
und wendet die folgende Operation ad infinitum an: gegebener Akkumulator{p,n}
, Ausgabep mod x
an den Stream. Stellen Sie dann den Akku auf{n,p+n}
.Der Rest:
quelle
SNOBOL4 (CSNOBOL4) , 153 Bytes
Probieren Sie es online!
quelle
Ruby ,
5553 BytesProbieren Sie es online!
quelle
JavaScript (ES6), 84 Byte
quelle
Python 3, 76 Bytes
Dies betrachtet einfach den längsten möglichen Zyklus von Fibonnaci-Zahlen (n ^ 2) und erstellt eine Liste aller Zahlen, die in dieser Zeit vorkommen. Zur Vereinfachung der Logik werden die Zahlen modulo n gespeichert.
quelle