Finde die fehlenden Zahlen in der Fibonacci-Sequenz Mod K

20

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

  • Standardlücken sind verboten .

  • Standard I / O .

  • Programme oder Funktionen sind akzeptabel .

  • 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 , also gewinnt die kürzeste Antwort in jeder Sprache.

Testfälle

Testfälle online generieren!

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

Verbunden:

Fibonacci-Bahnen zählen

Finden Sie die Pisano-Zeit

Pizzapants184
quelle
Sandbox (gelöscht).
Pizzapants184

Antworten:

6

Gelee , 9 8 Bytes

²RÆḞ%ḟ@Ḷ

Probieren Sie es online!

Basierend auf der Pisano-Zeit p(n) <= 6nvon A001175 . Auch p(n) <= 6n <= n^2für n >= 6und p(n) <= n^2für n < 6. Dieses Byte wurde dank Dennis gespeichert.

Meilen
quelle
²sollte funktionieren statt ×6.
Dennis
6

Haskell , 70 Bytes

Dank Esolanging Fruit konnten einige Bytes eingespart werden

8 Bytes dank Laikoni gespart

a=1:scanl(+)1a
f x=[u|u<-[2..x-1],and[mod b x/=u|(_,b)<-zip[1..x^2]a]]

Probieren Sie es online!

Weizen-Assistent
quelle
@EsolangingFruit Ah danke! Ich bin gerade selbst zu einem ähnlichen Schluss gekommen.
Weizen-Zauberer
read$showfunktioniert fromIntegerin diesem Fall nicht und spart zwei Bytes.
Laikoni
Verwenden Sie zip[1..x^2]zum Abschneiden, um weitere Bytes zu sparen: Probieren Sie es online aus!
Laikoni
@Laikoni Dauerte eine Weile, aber ich habe die Änderung vorgenommen. Danke, das ist eine gute Idee.
Wheat Wizard
5

Perl 6 ,  43 42 39  32 Bytes

{^$_ (-)(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Probier es aus

{^$_∖(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Probier es aus

{^$_∖(1,1,(*+*)%$_...{!$^a&&$^b==1})}

Probier es aus

{^$_∖(1,1,(*+*)%$_...!*&*==1)}

Probier es aus

Erweitert:

{  # bare block lambda with implicit parameter 「$_」

  ^$_               # Range upto and excluding the input

                   # set minus (U+2216)

  (                 # generate the Fibonacci sequence mod k

    1, 1,           # seed the sequece (can't be 0,1)

    ( * + * ) % $_  # add two values and modulus the input (lambda)

    ...             # keep doing that until

                    # it matches 0,1
    !*              #   negate the first param (1 when 0)
    &               #   and Junction
    *               #   second param
    == 1            #   both match 1

  )
}
Brad Gilbert b2gills
quelle
3

> <> 48 Bytes

01\
?!\:&+{:}%:1$0p&$:
v0\~:1=?
>?!;1-::0g?!nao:

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:

01\    Input is already on the stack
...... Initialises the sequence with 1 and 0
...... Goes to the second line
......

......
..\:&+{:}% Gets the next number in the modded Fibonacci sequence while preserving the previous number
......
......

......
..........:1$0p&$: Puts a 1 at that cell number on the first line
.......
.......

......             If the number is a 0 go to the third line
?!\..............: Check if the next number is a 1, meaning we've reached the end of the sequence
v0\~:1=?           Go to the fourth line if so
>.....             Re-add the 0 and go back to the second line if not

......           While input:
......             Get the cell from the first line
......             If not 0: print the number
>?!;1-::0g?!nao:   Finally, print a newline and decrement the input
Scherzen
quelle
3

MATL , 19 18 Bytes

0lbU:"yy+]vG\G:qX~

Probieren Sie es online!

-1 Byte danke an Guiseppe.

  bU:"   ]         % Do K^2 (>6K) times.
0l    yy+          %  Fibbonaci
                X~ % Set exclusive difference between
          vG\      %  the fibonacci numbers mod K
             G:q   %  and 0...K-1
Sanchises
quelle
18 Bytes ; Neuanordnung gewinnt Ihre Verwendung von X~!
Giuseppe
@ Giuseppe Danke! Immer noch sehr lang ....
Sanchises
2

Husk , 13 12 10 Bytes

Danke @Zgarb für -2 Bytes!

-U2m%⁰İfŀ⁰

Druckt eine leere Liste, falls alle ganzen Zahlen erscheinen, Probieren Sie es online aus!

Erläuterung

-U2m%⁰İfŀ⁰  -- named argument ⁰, example with: 8
-           -- difference of
        ŀ⁰  -- | lowered range: [0,1,2,3,4,5,6,7]
            -- and
      İf    -- | Fibonacci sequence: [1,1,2,3,5,8,13,21,34,55,89,144,233,377…
   m%⁰      -- | map (modulo ⁰): [1,1,2,3,5,0,5,5,2,7,1,0,1,1…
 U2         -- | keep longest prefix until 2 adjacent elements repeats: [1,1,2,3,5,0,5,5,2,7,1,0,1]
            -- : [4,6]
ბიმო
quelle
Mit können U2Sie das längste Präfix abrufen, bei dem sich kein benachbartes Paar wiederholt.
Zgarb
2

Python 3 , 78 Bytes

def m(K):M=0,1;exec(K*6*'M+=sum(M[-2:])%max(K,2),;'+'print({*range(K)}-{*M})')

Probieren Sie es online!

Druckt einen Satz, sodass die Ausgabe für leere Testfälle set()der leere Satz ist.

Erik der Outgolfer
quelle
@ovs meinst du in Python 2, oder? sicher
Erik der Outgolfer
2

R 92 86 Bytes

Vielen Dank an @ Giuseppe für das Speichern von 6 Bytes!

function(k,n=!!0:2){while(any((z=tail(n,2))-n[1:2]))n=c(n,sum(z)%%k);setdiff(1:k-1,n)}

Probieren Sie es online!

Ziemlich unkomplizierte Implementierung ( vorherige Version , aber dasselbe Konzept):

function(k,
         K=1:k-1,      #Uses default arguments to preset variables for legibility 
         n=c(0,1,1)){  #(wouldn't change byte-count to put them in the body of the function)
    while(any((z=tail(n,2))!=n[1:2])) #Do as long as first 2 elements are not identical to last 2 elements
        n=c(n,sum(z)%%k) #Built the fibonacci mod k sequence
    K[!K%in%n] #Outputs integers < k if not in sequence.
}
Plannapus
quelle
1
86 Bytes
Giuseppe
@ Giuseppe ah setdiff, gute Idee!
Plannapus
70 Bytes, die den 1:k^2Ansatz portieren, den alle anderen verwenden
Giuseppe
2

Python 3, 173 152 143 131 Bytes

f=lambda n,m,a=0,b=1:a%m if n<=0else f(n-1,m,b,a+b)
p=lambda n,i=2,y={0}:y^{*range(n)}if f(i,n)==1>f(i-1,n)else p(n,i+1,y|{f(i,n)})

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

Manish Kundu
quelle
Es ist ein Teil des Headers und muss nicht zwingend in den Code aufgenommen werden.
Manish Kundu
Okay, erledigt. @ovs Danke fürs Erzählen, ich wusste es nicht.
Manish Kundu
1
131 Bytes durch Erstellen von Mengen mit geschweiften Klammern anstelle von set()und verketteten Vergleichen.
Ovs
2

05AB1E , 10 Bytes

L<InLÅfI%K

Probieren Sie es online!

-3 Bytes dank Emigna.

Mr. Xcoder
quelle
@Emigna Ich habe für Ewigkeiten nach dem eingebauten gesucht! Vielen Dank!
Mr. Xcoder
2

Ruby , 47 Bytes

->n{a=b=1;[*1...n]-(1..n*n).map{a,b=b,a+b;a%n}}

Probieren Sie es online!

Obwohl es einige der gleichen Logik verwendet, basiert dies nicht auf GBs Antwort .

Erläuterung:

->n{
  a=b=1;   # start sequence with 1,1
  [*1...n] # all the numbers from 1 to n-1 as an array
           # 0 is excluded as it should never be in the final answer 
  -  # set operation; get all items in the first set and not in the second
  (1..n*n).map{ # n squared times
    a,b=b,a+b;  # assign next fibonacci numbers 
    a%n         # return a fibonacci number mod n
  }    # Map to an array
}
MegaTom
quelle
2

Common Lisp, 106 Bytes

(lambda(k)(do((a 1 b)c(b 1(mod(+ a b)k)))((=(1- b)0 a)(dotimes(i k)(or(member i c)(print i))))(push a c)))

Probieren Sie es online!

Renzo
quelle
1

Elixier , 148 144 Bytes

 fn x->Enum.to_list(1..x-1)--List.flatten Enum.take_while Stream.chunk(Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end),2),&Enum.sum(&1)!=1end

Probieren 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:

Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end)

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}, Ausgabe p mod xan den Stream. Stellen Sie dann den Akku auf{n,p+n} .

Der Rest:

fn x->                              Define a fxn f(x) that returns
  Enum.to_list(1..x-1)--            The numbers from 1..x-1 that are not in
  List.flatten                      The flattened list constructed by
    Enum.take_while                 Taking from mod-fib until
      Stream.chunk(                 A 2-size chunk
        Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end) (of mod fib)
        ,2)
      ,&Enum.sum(&1)!=1             sums to 1, representing [0,1] or [1,0]
end
Dave
quelle
1

JavaScript (ES6), 84 Byte

f=(n,a=0,b=1,q=[...Array(n).keys()])=>a*b+a-1?f(n,b,(a+b)%n,q,q[b]=0):q.filter(x=>x)
ETHproductions
quelle
1

Python 3, 76 Bytes

def t(n,r=[1]):
 while n*n>len(r):r+=[sum(r[-2:])%n]
 return{*range(n)}-{*r}

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.

user2699
quelle