Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Input: An integer 0 < n < 2^30, taken from stdin.

Output: The Pisano period of n (the length of the cycle of the Fibonacci sequence mod n)

Input is smaller than 2^30 so that intermediate values are all less than 2^31.

Shortest code wins.

Test cases

Input: 1 Output: 1

Input: 2 Output: 3

Input: 10 Output: 60

share|improve this question
2  
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
1  
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. –  boothby 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
2  
@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. –  boothby Dec 6 '13 at 19:35
    
Wait, where does it say 6n? I must have missed it. In any case, I'm pretty sure the math still says that 6n will blow out a signed 32-bit integer before we hit 2^30. –  Iszi Dec 6 '13 at 19:45

7 Answers 7

up vote 6 down vote accepted

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.

share|improve this answer

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.

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

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
share|improve this answer

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
share|improve this answer
    
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN) Oh god, that's some order of operation exploitation right there. –  GigaWatt Oct 25 '12 at 17:11

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
share|improve this answer
    
Thanks, beary605, for the additional golfing! –  ESultanik 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. –  David Carraher 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. –  ESultanik Oct 21 '12 at 19:28
    
I use a routine furnished by Wolfram Research. It counts necessary white space, I think. –  David Carraher 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. –  Strigoides Oct 21 '12 at 23:24

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

share|improve this answer
    
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) –  beary605 Oct 23 '12 at 23:36
    
append actually has a different functionality than +=. Thanks for the tips though. –  scleaver Oct 24 '12 at 18:35
    
I think it works the same way in this case. –  beary605 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). –  primo Oct 27 '12 at 7:21
    
Ah ok, my mistake was that I was using a+=c instead of a+=[c] –  scleaver Oct 29 '12 at 17:07

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.