Find the Pisano Period

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.

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 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
• Limitation to 2^30 may ensure all intermediate values are less than 2^31 but it still doesn't guarantee that the Pisano Period will fit within a 32-bit signed integer. (I presume that's the reason for your limitation?) Pisano Periods can be significantly larger than their n. For example, the Pisano Period of 6 is 24. Powers of 10 above 100 come out 50 percent larger than n.
– Iszi
Dec 6 '13 at 5:34
• Pigeonhole principle says that f(i),f(i+1) can take at most n^2 values mod n. Thus, n limited to 2^30 could wind up producing a period of up to 2^60. Restricting n <= 2^16 would give P(n) <= 2^32. Dec 6 '13 at 14:24
• @boothby I'm not quite sure I understand what you're saying, or if it's even properly addressing the same problem I am. Could you explain a bit further, perhaps with additional links? Feel free to pull me into chat if needed.
– Iszi
Dec 6 '13 at 17:39
• @Iszi Observe that f(i+2) = f(i+1)+f(i), so the 'state' of a machine looping over the period can be described with a pair of integers mod n. There are at most n^2 states, so the period is at most n^2. Oh! Wikipedia claims that the period is at most 6n. Nevermind my triviality. Dec 6 '13 at 19:35
• oeis.org/A001175 Feb 21 '17 at 20:27

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.

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.

• Does this handle input 1 correctly? Oct 22 '12 at 12:20
• @PeterTaylor Nope, didn't test that corner case. Back to the drawing board. Oct 22 '12 at 12:35
• @PeterTaylor The new code also works for input 1 - and still only 24 chars. Oct 23 '12 at 5:27

Python, 18813210195 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

$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 • Thanks, beary605, for the additional golfing! Oct 21 '12 at 16:00 • You may want to count your chars again. My count of your response is below your count of your response. Oct 21 '12 at 19:01 • @David: Are you counting whitespace? I just double-checked (by catting to wc -c and I get the same number. Oct 21 '12 at 19:28 • I use a routine furnished by Wolfram Research. It counts necessary white space, I think. Oct 21 '12 at 19:53 • if k>0 and s[0:k]==s[k:]:break can be changed to if s and s[:k]==s[k:]:break. You can also cut down significantly by removing the iterator, changing the for loop to while 1:, and performing a,b=a,a+b at the end of the while loop. Oct 21 '12 at 23:24 Python 9085969490 82 n=input();c=[1,1];a=[] while(c in a)<1%n:a+=[c];c=[c,sum(c)%n] print len(a)or 1 Edit: Implemented suggestions by beary and primo • 85: a.append(c) -> a+=[c], while loop can be put onto a single line, ((n>1)>>(c in a)) -> (n>1)>>(c in a) Oct 23 '12 at 23:36 • append actually has a different functionality than +=. Thanks for the tips though. Oct 24 '12 at 18:35 • I think it works the same way in this case. Oct 25 '12 at 0:12 • (n>1)>>(c in a) -> (c in a)<1%n for 3 bytes. And I agree with beary about the append. Whether you append a reference to c, or extend a by the value of c, it's exactly the same either way (as you immediately destroy your reference to c anyway). Oct 27 '12 at 7:21 • Ah ok, my mistake was that I was using a+=c instead of a+=[c] Oct 29 '12 at 17:07 Mathematica 73 p = {1, 0}; j = 0; q = p; While[j++; s = Mod[Plus @@ p, n]; p = RotateLeft@p; p[] = s; p != q]; j 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 • 1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN) Oh god, that's some order of operation exploitation right there. Oct 25 '12 at 17:11

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

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. Perl, 75, 61, 62 + 1 = 63$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)until$h{"$m,$k"}++;say$a-1

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

• You can get rid of $n=<>; (-6) and replace it with the -n flag (+1), then all instances of$n can be replaced with $_. You can use -M5.010 for free, which lets you use the say command instead of print (-2). Modifier while statements do not need parentheses around the condition (-2). Instead of @{[%h]}/2, you can have a counter$a++, before ($m,$k)= and then just have say$a-1 at the end (-2). Instead of "$m,$k" use$m.$k (-2). This should come out to$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1 with the -n flag, for 61 + 1 = 62 bytes. Dec 20 '16 at 14:55
• Clearly I'm not as clever with Perl as I thought I was. Thanks for the tips. Dec 20 '16 at 18:34
• There are a lot of useful pointers in the Tips for golfing in Perl thread! Good luck! ^^ Dec 20 '16 at 18:37
• Actually, I was wrong -- you need "$m,$k" instead of $m.$k, (+2), but you can save 1 byte by changing while!$h to until$h (-1). Sorry! Dec 20 '16 at 19:22
• Hm? Under what input does $m.$k fail? It seemed to work on my end. Dec 20 '16 at 19:33

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

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

05AB1E, 13 bytes

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

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)