Find the Pisano Period

Question

The Fibonacci sequence is a well know sequence in which each entry is the sum of the previous two and the first two entries are 1. If we take the modulo of each term by a constant the sequence will become periodic. For example if we took decided to compute the sequence mod 7 we would get the following:

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

This has a period of 16. A related sequence, called the Pisano sequence, is defined such that a(n) is the period of the fibonacci sequence when calculated modulo n.

Task

You will should write a program or function that when given n will compute and output the period of the Fibonacci sequence mod n. That is the nth term in the Pisano sequence.

You must only support integers on the range 0 < n < 2^30

This is a code-golf competition so you should aim to minimize the size of your source code as scored by bytes.

Test cases

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

Answer 1

GolfScript (28 25 24 23 chars)

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

Takes input in stdin, leaves it on stdout (or the stack, if you want to further process it...)

This correctly handles the corner cases (Demo).

As a point of interest to GolfScript programmers, I think this is the first program I've written with an unfold which actually came out shorter than the other approaches I tried.

Answer 2

GolfScript, 24 characters

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

Next iteration of a GolfScript implementation. The second version now also handles 1 correctly. It became quite long but maybe someone can find a way to shorten this version. You can try above version online.

Answer 3

Python, 188 132 101 95 87 characters

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

Usage

$ echo 10 | python pisano.py
60

For example:

$ 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

Answer 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: Implemented suggestions by beary and primo

Answer 5

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

Answer 6

PHP - 61 57 bytes

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

This script will erroneously report 2 for n=1, but all other values are correct.

Sample I/O, a left-truncable series where π(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

Answer 7

Husk, 9 bytes

LU_2M`%İf

Try it online!

Explanation

I'm not sure if I've ever used U with a negative argument before.

LU_2M`%İf  Implicit input, say n=8.
       İf  Infinite list of Fibonacci numbers:
             [1,1,2,3,5,8,13,21..
    M      Map
     `%    modulo n:
             [1,1,2,3,5,0,5,5,2,7,1,0,1,1,2..
 U_2       Cut at the start of first repeated sublist of length 2 (here [1,1]):
             [1,1,2,3,5,0,5,5,2,7,1,0]
L          Length: 12

Answer 8

PowerShell: 98

Golfed 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, with comments:

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

---

Notes:

I'm not sure exactly what the maximum reliable limit is for $n with this script. It's quite possibly less than 2^30, as $x could possibly overflow an int32 before $n gets there. Besides that, I haven't tested the upper limit myself because run times for the script already hit around 30 seconds on my system for $n=1e7 (which is only a bit over 2^23). For the same reason, I'm not quickly inclined to test and troubleshoot whatever additional syntax may be needed to upgrade the variables to uint32, int64, or uint64 where needed in order to expand this script's range.

---

Sample output:

I wrapped this in another for loop:

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

Then set $n=$i instead of =read-host, and changed the output to "$i | $x" to get an idea of the script's general reliability. Here's some of the output:

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: I'm not really sure how some Pisano Periods are significantly shorter than $n. Is this normal, or is something wrong with my script? Nevermind - I just remembered that, after 5, Fibonacci numbers quickly become much larger than their place in the sequence. So, this makes total sense now.

Answer 9

Perl, 75, 61, 62 + 1 = 63

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

Usage

$ 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 for -n flag. Shaved off 13 bytes thanks to Gabriel Benamy.

Answer 10

APL (Dyalog Extended), 21 bytes

{≢(⍵|1⌽+\)⌂traj⍵|1 1}

Try it online!

An anonymous function (dfn) that takes n as its right argument.

How it works

{≢(⍵|1⌽+\)⌂traj⍵|1 1}  ⍝ Anonymous function; Input ⍵←n
{                1 1}  ⍝ Two ones (initial two values of Fibonacci)
               ⍵|      ⍝ Modulo n (to handle special case)
  (      )⌂traj        ⍝ Repeat and collect until the same value appears...
     1⌽+\              ⍝   (a,b) → (a+b,a)
   ⍵|                  ⍝   Modulo n
 ≢                     ⍝ Count the iterations before the same value appears

Answer 11

Clojure, 102 bytes

Not too exciting, iterates the formula until we reach back [1 1] (I hope this is always the case). Special handling of (f 1) as it converges to [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))

Answer 12

05AB1E, 13 bytes

∞.Δ∞ÅfI%sô3£Ë

Try it online or verify all test cases.

Explanation:

∞.Δ            # Find the first positive integer which is truthy for:
   ∞           #  Push a positive infinite list
    Åf         #  Get the n'th Fibonacci number of each value `n` in this list
      I%       #  Take modulo the input on each Fibonacci number
        s      #  Swap so the current integer is at the top of the stack
         ô     #  Split the infinite modular Fibonacci list into parts of that size
          3£   #  Only leave the first 3 parts
            Ë  #  And check if all three sublist parts are the same
               # (after which the result is output implicitly)