The Fibonacci urutan adalah urutan baik tahu di mana setiap entri adalah jumlah dari dua sebelumnya dan dua entri pertama adalah 1. Jika kita mengambil modulo setiap istilah dengan konstan urutan akan menjadi periodik. Sebagai contoh jika kita memutuskan untuk menghitung urutan mod 7 kita akan mendapatkan yang berikut:

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

Ini memiliki periode 16. Urutan terkait, yang disebut urutan Pisano , didefinisikan sedemikian rupa sehingga a(n)merupakan periode urutan fibonacci ketika dihitung modulo n.

Tugas

Anda harus menulis sebuah program atau fungsi yang ketika diberikan nakan menghitung dan mengeluarkan periode mod urutan Fibonacci n. Itu adalah istilah ke-n dalam urutan Pisano.

Anda hanya harus mendukung bilangan bulat pada rentang tersebut 0 < n < 2^30

Ini adalah kompetisi kode-golf sehingga Anda harus berusaha meminimalkan ukuran kode sumber Anda karena dinilai oleh byte.

Uji kasus

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

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

Mengambil input di stdin, membiarkannya di stdout (atau stack, jika Anda ingin memprosesnya lebih lanjut ...)

Ini dengan benar menangani kasing sudut ( Demo ).

Sebagai hal yang menarik bagi programmer GolfScript, saya pikir ini adalah program pertama yang saya tulis dengan lipatan yang sebenarnya lebih pendek daripada pendekatan lain yang saya coba.

GolfScript, 24 karakter

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

Iterasi selanjutnya dari implementasi GolfScript. Versi kedua sekarang juga menangani 1 dengan benar. Itu menjadi cukup lama tetapi mungkin seseorang dapat menemukan cara untuk mempersingkat versi ini. Anda dapat mencoba versi di atas secara online .

Python, 188 132 101 95 87 karakter

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

Pemakaian

$ echo 10 | python pisano.py
60

Sebagai contoh:

$ 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

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

Sunting: Saran yang diterapkan oleh beary dan 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 byte

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

Script ini keliru akan melaporkan 2untuk n=1, tetapi semua nilai-nilai lain yang benar.

Sampel I / O, seri terpotong kiri di mana π (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

Kode golf:

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

Tidak disatukan, dengan komentar:

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

Catatan:

Saya tidak yakin persis apa batas maksimum yang dapat diandalkan untuk $ n dengan skrip ini. Kemungkinannya kurang dari 2 ^ 30, karena $ x mungkin bisa meluap int32 sebelum $ n sampai di sana. Selain itu, saya sendiri belum menguji batas atas karena waktu berjalan untuk skrip sudah mencapai sekitar 30 detik pada sistem saya untuk $ n = 1e7 (yang hanya sedikit lebih dari 2 ^ 23). Untuk alasan yang sama, saya tidak cenderung untuk menguji dan memecahkan masalah sintaks tambahan apa pun yang mungkin diperlukan untuk memutakhirkan variabel ke uint32, int64, atau uint64 jika diperlukan untuk memperluas jangkauan skrip ini.

Output sampel:

Saya membungkus ini di lain untuk loop:

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

Kemudian atur $n=$ialih-alih =read-host, dan ubah output "$i | $x"untuk mendapatkan gagasan tentang keandalan umum skrip. Berikut beberapa hasilnya:

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: Saya tidak begitu yakin bagaimana beberapa Periode Pisano secara signifikan lebih pendek dari $ n. Apakah ini normal, atau ada yang salah dengan skrip saya? Nevermind - Saya baru ingat bahwa, setelah 5, angka-angka Fibonacci dengan cepat menjadi jauh lebih besar daripada tempat mereka dalam urutan. Jadi, ini masuk akal sekarang.

Perl, 75 , 61 , 62 + 1 = 63

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

Pemakaian

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

Tidak disatukan

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

+1 byte untuk -nbendera. Mencukur 13 byte berkat Gabriel Benamy.

Clojure, 102 byte

Tidak terlalu mengasyikkan, mengulang formula sampai kita mencapai kembali [1 1](saya harap ini selalu terjadi). Penanganan khusus (f 1)saat menyatu [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))