Sekwencja Fibonacciego jest sekwencją dobrze wiedzieć, w którym każdy wpis jest sumą dwóch poprzednich i pierwszych dwóch pozycjach są: 1. Jeśli weźmiemy modulo każdego terminu przez stałą sekwencję staną się okresowe. Na przykład, jeśli zdecydujemy się obliczyć mod sekwencyjny 7, otrzymamy:

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

Ma to okres 16. Powiązana sekwencja, zwana sekwencją Pisano , jest zdefiniowana tak, że a(n)jest to okres sekwencji Fibonacciego przy obliczaniu modułu.

Zadanie

Powinieneś napisać program lub funkcję, która, gdy nzostanie podana , obliczy i wyświetli okres modyfikacji sekwencji Fibonacciegon . To jest n-ty termin w sekwencji Pisano.

Musisz obsługiwać tylko liczby całkowite w zakresie 0 < n < 2^30

To jest golf golfowy zawody w więc powinieneś dążyć do zminimalizowania rozmiaru kodu źródłowego według liczby bajtów.

Przypadki testowe

1  -> 1
2  -> 3
3  -> 8
4  -> 6
5  -> 20
6  -> 24
7  -> 16
8  -> 12
9  -> 24
10 -> 60
11 -> 10
12 -> 24

GolfScript ( 28 25 24 23 znaków)

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

Pobiera dane wejściowe na standardowe wejście, pozostawia je na standardowe wyjście (lub stos, jeśli chcesz dalej przetwarzać ...)

To poprawnie obsługuje skrzynie narożne ( Demo ).

Jako przedmiot zainteresowania programistów GolfScript, myślę, że jest to pierwszy program, który napisałem z rozwinięciem, który faktycznie wyszedł krótszy niż inne podejścia, których próbowałem.

GolfScript, 24 znaki

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

Następna iteracja implementacji GolfScript. Druga wersja obsługuje teraz również poprawnie 1. Stało się dość długo, ale może ktoś może znaleźć sposób na skrócenie tej wersji. Możesz wypróbować powyższą wersję online .

Python, 188 132 101 95 87 znaków

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

Stosowanie

$ echo 10 | python pisano.py
60

Na przykład:

$ 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

Pyton 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

Edycja: Zaimplementowane sugestie beary i primo

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

PHP - 61 57 bajtów

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

Ten skrypt błędnie zgłaszać 2na n=1, ale wszystkie inne wartości są prawidłowe.

Próbki we / wy, seria skróconych w lewo, gdzie π (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

PowerShell: 98

Kod do gry w golfa:

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)}

Niegolfowany, z komentarzami:

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

Uwagi:

Nie jestem pewien, jaki jest maksymalny wiarygodny limit dla $ n dla tego skryptu. Jest to prawdopodobnie mniej niż 2 ^ 30, ponieważ $ x może przepełnić int32, zanim $ n dotrze. Poza tym sam nie testowałem górnego limitu, ponieważ czasy uruchamiania skryptu osiągnęły już około 30 sekund w moim systemie za $ n = 1e7 (czyli nieco ponad 2 ^ 23). Z tego samego powodu nie jestem skłonny szybko testować i rozwiązywać problemów z jakąkolwiek dodatkową składnią, która może być potrzebna do uaktualnienia zmiennych do uint32, int64 lub uint64 w razie potrzeby w celu rozszerzenia zakresu tego skryptu.

Przykładowe dane wyjściowe:

Zapakowałem to w inną pętlę for:

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

Następnie ustaw $n=$izamiast =read-hosti zmień dane wyjściowe, aby "$i | $x"zorientować się w ogólnej niezawodności skryptu. Oto niektóre wyniki:

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

Sidenote: Nie jestem do końca pewien, jak niektóre Okresy Pisano są znacznie krótsze niż $ n. Czy to normalne, czy coś jest nie tak z moim skryptem? Nieważne - właśnie przypomniałem sobie, że po 5, liczby Fibonacciego szybko stają się znacznie większe niż ich miejsce w sekwencji. To ma teraz sens.

Perl, 75 , 61 , 62 + 1 = 63

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

Stosowanie

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

Nie golfił

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

+1 bajt dla -nflagi. Ogolono 13 bajtów dzięki Gabrielowi Benamy'emu.

Clojure, 102 bajty

Niezbyt ekscytujące, iteruje formułę, dopóki nie wrócimy [1 1](mam nadzieję, że zawsze tak jest). Specjalna obsługa w (f 1)miarę konwergencji [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))