Finden Sie die Pisano-Zeit

20

Die Fibonacci-Folge ist eine bekannte Folge, in der jeder Eintrag die Summe der beiden vorhergehenden und die ersten beiden Einträge 1 ist. Wenn wir das Modulo jedes Terms mit einer Konstanten nehmen, wird die Folge periodisch. Wenn wir uns zum Beispiel dazu entschließen, die Sequenz Mod 7 zu berechnen, erhalten wir Folgendes:

1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...

Dies hat eine Periode von 16. Eine verwandte Sequenz, die Pisano-Sequenz genannt wird , ist so definiert, dass dies a(n)die Periode der Fibonacci-Sequenz ist, wenn sie modulo n berechnet wird.

Aufgabe

Sie sollten ein Programm oder eine Funktion schreiben, die bei Angabe ndie Periode des Fibonacci-Sequenzmods berechnet und ausgibt n. Dies ist der n-te Term in der Pisano-Sequenz.

Sie müssen nur Ganzzahlen im Bereich unterstützen 0 < n < 2^30

Dies ist ein Wettbewerb, daher sollten Sie versuchen, die Größe Ihres Quellcodes nach Bytes zu minimieren.

Testfälle

1  -> 1
2  -> 3
3  -> 8
4  -> 6
5  -> 20
6  -> 24
7  -> 16
8  -> 12
9  -> 24
10 -> 60
11 -> 10
12 -> 24
Pappschachtel
quelle
3
Die Beschränkung auf 2 ^ 30 kann sicherstellen, dass alle Zwischenwerte kleiner als 2 ^ 31 sind, garantiert jedoch nicht, dass die Pisano-Periode in eine 32-Bit-Ganzzahl mit Vorzeichen passt. (Ich nehme an, das ist der Grund für Ihre Einschränkung?) Pisano-Perioden können erheblich größer sein als ihre n . Zum Beispiel ist die Pisano-Periode von 6 gleich 24. Potenzen von 10 über 100 sind 50 Prozent größer als n .
Iszi
3
Das Pigeonhole-Prinzip besagt, dass f(i),f(i+1)höchstens n^2Werte mod annehmen können n. Somit könnte nbegrenzt auf 2^30einen Zeitraum von bis zu produzieren 2^60. Einschränkung n <= 2^16würde geben P(n) <= 2^32.
Stand
@boothby Ich bin nicht ganz sicher, ob ich verstehe, was du sagst, oder ob es überhaupt das gleiche Problem betrifft, das ich bin. Könnten Sie das etwas näher erläutern, vielleicht mit zusätzlichen Links? Fühlen Sie sich frei, mich in den Chat zu ziehen, wenn nötig.
Iszi
2
@Iszi Beachten Sie f(i+2) = f(i+1)+f(i), dass der 'Status' einer Maschine, die über den Zeitraum eine Schleife durchläuft, mit einem Paar Ganzzahlen mod beschrieben werden kann n. Es gibt höchstens n^2Staaten, also höchstens eine Periode n^2. Oh! Wikipedia behauptet, dass die Periode höchstens ist 6n. Vergiss meine Trivialität.
Stand
2
oeis.org/A001175
Digitales Trauma

Antworten:

11

GolfScript ( 28 25 24 23 Zeichen)

~1.{(2$+}{.@+2$%}/+\-,)

Nimmt die Eingabe in stdin auf, belässt sie auf stdout (oder auf dem Stack, wenn Sie sie weiter verarbeiten möchten ...)

Dies behandelt die Eckfälle korrekt ( Demo ).

Aus Gründen des Interesses für GolfScript-Programmierer denke ich, dass dies das erste Programm ist, das ich mit einer Entfaltung geschrieben habe, die tatsächlich kürzer ausfiel als die anderen Ansätze, die ich ausprobiert habe.

Peter Taylor
quelle
7

GolfScript, 24 Zeichen

~:&1.{.2$+&%.2$(|}do](-,

Nächste Iteration einer GolfScript-Implementierung. Die zweite Version behandelt nun auch 1 korrekt. Es wurde ziemlich lang, aber vielleicht kann jemand einen Weg finden, diese Version zu verkürzen. Sie können die obige Version online testen .

Howard
quelle
Wird die Eingabe von diesem Handle 1korrekt verarbeitet?
Peter Taylor
@PeterTaylor Nope, hat diesen Eckfall nicht getestet. Zurück zum Zeichenbrett.
Howard
@PeterTaylor Der neue Code funktioniert auch für die Eingabe 1- und immer noch nur 24 Zeichen.
Howard
4

Python, 188 132 101 95 87 Zeichen

n=input()
s=[]
a=k=0
b=1
while s[:k]!=s[k:]or k<1:s+=[a%n];k=len(s)/2;a,b=b,a+b
print k

Verwendung

$ echo 10 | python pisano.py
60

Beispielsweise:

$ for i in {1..50}; do; echo $i | python pisano.py; done
1
3
8
6
20
24
16
12
24
60
10
24
28
48
40
24
36
24
18
60
16
30
48
24
100
84
72
48
14
120
30
48
40
36
80
24
76
18
56
60
40
48
88
30
120
48
32
24
112
300
ESultanik
quelle
Danke, beary605 , für das zusätzliche Golfen!
ESultanik
Möglicherweise möchten Sie Ihre Zeichen erneut zählen. Meine Anzahl Ihrer Antworten liegt unter Ihrer Anzahl Ihrer Antworten.
DavidC
@ David: Zählst du Whitespace? Ich habe doppelt geprüft (durch catting zu wc -cund ich die gleiche Nummer.
ESultanik
Ich benutze eine Routine von Wolfram Research. Es zählt notwendiger weißer Raum, denke ich.
DavidC
if k>0 and s[0:k]==s[k:]:breakkann geändert werden zu if s and s[:k]==s[k:]:break. Sie können auch erheblich reduzieren, indem Sie den Iterator entfernen, die forSchleife auf ändern while 1:und a,b=a,a+bam Ende der while-Schleife ausführen .
Strigoides
4

Python 90 85 96 94 90 82

n=input();c=[1,1];a=[]
while(c in a)<1%n:a+=[c];c=[c[1],sum(c)%n]
print len(a)or 1

Edit: Vorschläge von beary und primo umgesetzt

scleaver
quelle
85 a.append(c) -> a+=[c]((n>1)>>(c in a)) -> (n>1)>>(c in a)
:,
appendhat tatsächlich eine andere Funktionalität als +=. Vielen Dank für die Tipps.
Scleaver
Ich denke, dass es in diesem Fall genauso funktioniert.
beary605
(n>1)>>(c in a) -> (c in a)<1%nfür 3 Bytes. Und ich stimme Beary in Bezug auf den Anhang zu. Unabhängig davon, ob Sie einen Verweis anfügen coder um aden Wert von erweitern c, ist dies in beiden Fällen genauso (da Sie den Verweis auf csowieso sofort zerstören ).
Primo
Ah ok, mein Fehler war, dass ich a+=cstatta+=[c]
scleaver 29.10.12
2

Mathematica 73

p = {1, 0}; j = 0; q = p;
While[j++; s = Mod[Plus @@ p, n]; p = RotateLeft@p; p[[2]] = s; p != q]; j
DavidC
quelle
2

PHP - 61 57 Bytes

<?for(;1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN););echo$i;

Dieses Skript wird fälschlicherweise berichten 2für n=1, aber alle anderen Werte korrekt sind.

Sample I / O, eine links abschneidbare Reihe mit π (n) = 2n + 2:

$ echo 3 | php pisano.php
8
$ echo 13 | php pisano.php
28
$ echo 313 | php pisano.php
628
$ echo 3313 | php pisano.php
6628
$ echo 43313 | php pisano.php
86628
$ echo 543313 | php pisano.php
1086628
$ echo 4543313 | php pisano.php
9086628
$ echo 24543313 | php pisano.php
49086628
primo
quelle
1
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)Oh Gott, das ist genau dort, wo es um die Ausbeutung von Operationen geht.
Mr. Llama
1

PowerShell: 98

Golf Code:

for($a,$b=0,(1%($n=read-host))){$x++;if($a+$b-eq0-or("$a$b"-eq10)){$x;break}$a,$b=$b,(($a+$b)%$n)}

Ungolfed, mit Kommentaren:

for
(
    # Start with $a as zero, and $b as 1%$n.
    # Setting $b like this at the start helps catch the exceptional case where $n=1.
    $a,$b=0,(1%
    (
        # Grab user input for n.
        $n=read-host
    ))
)
{
    # Increasing the counter ($x) and testing for the end of the period at the start ensures proper output for $n=1.
    $x++;

    # Test to see if we've found the end of the Pisano Period.
    if
    (
        # The first part catches $n=1, since $a and $b will both be zero at this point.
        $a+$b-eq0-or
        (
            # A shorter way of testing $a-eq1-and$b-eq0, which is the end of a "normal" Pisano Period.
            "$a$b"-eq10
        )
    )
    {
        # Pisano Period has reached its end. Output $x and get out of the loop.
        $x;break
    }

    # Pisano Period still continues, perform operation to calculate next number.
    # Works pretty much like a Fibonacci sequence, but uses ($a+$b)%$n for the new $b instead.
    # This takes advantage of the fact we don't really need to track the actual Fibonacci numbers, just the Fibonacci pattern of %$n.
    $a,$b=$b,(($a+$b)%$n)
}

# Variable cleanup - not included in golfed code.
rv n,a,b,x

Anmerkungen:

Ich bin mir nicht sicher, wie hoch das maximale zuverlässige Limit für $ n mit diesem Skript ist. Es ist ziemlich wahrscheinlich weniger als 2 ^ 30, da $ x möglicherweise ein int32 überlaufen könnte, bevor $ n dort ankommt. Außerdem habe ich die Obergrenze nicht selbst getestet, da die Laufzeit des Skripts auf meinem System bereits 30 Sekunden für $ n = 1e7 betrug (was nur etwas über 2 ^ 23 liegt). Aus dem gleichen Grund bin ich nicht schnell dazu geneigt, zusätzliche Syntax zu testen und Fehler zu beheben, die zum Aktualisieren der Variablen auf uint32, int64 oder uint64 erforderlich sind, um den Bereich dieses Skripts zu erweitern.


Beispielausgabe:

Ich habe dies in eine andere for-Schleife eingewickelt:

for($i=1;;$i++)

Setzen Sie dann $n=$istatt =read-hostund ändern Sie die Ausgabe, "$i | $x"um sich ein Bild von der allgemeinen Zuverlässigkeit des Skripts zu machen. Hier sind einige der Ausgaben:

1 | 1
2 | 3
3 | 8
4 | 6
5 | 20
6 | 24
7 | 16
8 | 12
9 | 24
10 | 60
11 | 10
12 | 24
13 | 28
14 | 48
15 | 40
16 | 24
17 | 36
18 | 24
19 | 18
20 | 60

...

9990 | 6840
9991 | 10192
9992 | 624
9993 | 4440
9994 | 1584
9995 | 6660
9996 | 1008
9997 | 1344
9998 | 4998
9999 | 600
10000 | 15000
10001 | 10212
10002 | 3336
10003 | 5712
10004 | 120
10005 | 1680
10006 | 10008
10007 | 20016
10008 | 552
10009 | 3336
10010 | 1680

Nebenbemerkung: Ich bin mir nicht sicher, wie einige Pisano-Perioden deutlich kürzer als $ n sind. Ist das normal oder stimmt etwas mit meinem Skript nicht? Nevermind - Ich habe mich gerade daran erinnert, dass Fibonacci-Zahlen nach 5 sehr schnell viel größer werden als ihre Position in der Sequenz. Das macht jetzt also Sinn.

Iszi
quelle
1

Perl, 75 , 61 , 62 + 1 = 63

$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)until$h{"$m,$k"}++;say$a-1

Verwendung

$ echo 8 | perl -n -M5.010 ./pisano.pl
12

Ungolfed

$k = 1 % $_;
$a++, ($m, $k) = ($k, ($m + $k) % $_) until $h{"$m,$k"}++;
say $a - 1

+1 Byte für -nFlag. Dank Gabriel Benamy 13 Bytes gespart.

Silvio Mayolo
quelle
1
Sie können $n=<>;(-6) loswerden und durch das -nFlag (+1) ersetzen , dann können alle Instanzen von $ndurch ersetzt werden $_. Sie können -M5.010kostenlos verwenden, wodurch Sie den sayBefehl anstelle von print(-2) verwenden können. Modifikatoranweisungen whilebenötigen keine Klammern um die Bedingung (-2). Stattdessen @{[%h]}/2können Sie einen Zähler $a++,vor ($m,$k)=und dann nur say$a-1am Ende haben (-2). Anstelle von "$m,$k"use $m.$k(-2). Dies sollte $k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1mit dem -nFlag für 61 + 1 = 62 Bytes erreicht werden.
Gabriel Benamy
Offensichtlich bin ich mit Perl nicht so schlau, wie ich dachte. Danke für die Tipps.
Silvio Mayolo
Die Tipps zum Golfen im Perl- Thread enthalten viele nützliche Hinweise ! Viel Glück! ^^
Gabriel Benamy
Eigentlich habe ich mich geirrt - Sie brauchen "$m,$k"statt $m.$k(+2), aber Sie können 1 Byte sparen, indem Sie while!$hauf until$h(-1) wechseln . Es tut uns leid!
Gabriel Benamy
Hm? Unter welchen Eingaben $m.$kscheitert das? Es schien an meinem Ende zu arbeiten.
Silvio Mayolo
0

Clojure, 102 Bytes

Nicht zu aufregend, iteriert die Formel, bis wir zurückkommen [1 1](ich hoffe, das ist immer der Fall). Besondere Behandlung (f 1)wie es konvergiert [0 0].

#(if(< % 2)1(+(count(take-while(fn[v](not=[1 1]v))(rest(iterate(fn[[a b]][b(mod(+ a b)%)])[1 1]))))1))
NikoNyrh
quelle