Find the Pisano Period of a number

Question

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

Peter Taylor · Accepted Answer · 2012-10-23 16:31:03Z

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.

Howard · Answer 2 · 2012-10-23 05:26:33Z

up vote 3 down vote

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.

edited Oct 23 '12 at 5:26

answered Oct 22 '12 at 8:23

Howard
6,2651721

	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

primo · Answer 3 · 2012-10-22 16:08:02Z

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.

beary605 · Answer 4 · 2012-10-25 12:55:41Z

up vote 1 down vote

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

edited Oct 25 '12 at 12:55

beary605
1,4931218

answered Oct 21 '12 at 14:04

ESultanik
56827

	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 `cat`ting 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

show 2 more comments

scleaver · Answer 5 · 2012-10-29 17:15:36Z

up vote 1 down vote

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

edited Oct 29 '12 at 17:15

answered Oct 22 '12 at 15:55

scleaver
3915

	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

David Carraher · Answer 6 · 2012-10-21 18:53:18Z

up vote 0 down vote

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

answered Oct 21 '12 at 18:53

David Carraher
3,3891422

asked	6 months ago
viewed	456 times
active	6 months ago

Find the Pisano Period of a number

Test cases

6 Answers

GolfScript (28 25 24 23 chars)

GolfScript, 24 characters

PHP - 61 57 bytes

Python, 188 132 101 95 87 characters

Usage

Python 90 85 96 94 90 82

Mathematica 73

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math language-agnostic number fibonacci or ask your own question.

Find the Pisano Period of a number

Test cases

6 Answers

GolfScript (28 25 24 23 chars)

GolfScript, 24 characters

PHP - 61 57 bytes

Python, 188 132 101 95 87 characters

Usage

Python 90 85 96 94 90 82

Mathematica 73

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math language-agnostic number fibonacci or ask your own question.

Related