Modular Fibonacci Cycles

Question

The Fibonacci sequence is a well known and famous sequence, where each successive element is the sum of the previous two. A modular Fibonacci sequence is the same, except that the addition is performed over a finite field, or to put it another way, a modulo operation is performed after each addition.

For instance, the modular Fibonacci sequence with starting values 1, 1 and modulus 5 is:

1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, ...

At this point, the sequence is once again 1, 1, and so the sequence will repeat, cyclically, with a cycle length of 20.

Your challenge is to find the (minimal) cycle length for a specific starting pair and modulus, in the fewest bytes.

Details: The initial values will both be in the range 0 <= i,j < m, where m is the modulus. The initial values will not both be zero, and the modulus will be at least 2. You may take the input in any standard means or format, in any order, function, program or similar, and output via return or print. Standard loopholes apply.

Examples:

First element, second element, modulus:

1, 1, 5 => 20
1, 1, 4 => 6
2, 4, 6 => 8
3, 3, 6 => 3

This is code golf - shortest code in bytes wins. Good luck!

Answer 1

Python, 56

g=lambda a,b,m,u=0:u!=(a,b)and-~g(b,(a+b)%m,m,u or(a,b))

Answer 2

Retina, 69 61 bytes

This was great fun to write!

(1* )(1*).*
x$2$1$0
(1*)(?=.* \1$)

)`x(1* 1*) .* \1 .*
x
x
1

Each line should go to its own file but you can run the code as one file with the -s flag.

Takes input in unary, in format j i m and gives output in unary.

The four substitution pairs do the followings:

• Add next element and increase step counter.
• Take modulo of the new element.
• If we reached the starting numbers delete everything except step counter. This will break the loop of the first three steps.
• Convert step count to unary number.

The string has the following format during the computation (with (?#comments)):

x*(?#number of steps)(1* )+(?#sequence, reversed)1*(?#modulus)

The code makes use of some observations:

• The modulus can be part of the sequence as it is bigger than any other number causing no false positive match.
• There will always be a number between the two repeating pair. I.e.output will always be at least 3. (The 3rd number can be the same as the 1st if the sequence starts as x,0,x,x,...)
• You have to subtract the modulo from the new number at most once.

Every substitution step shown in its own line for the example j=1, i=1, m=4:

1 1 1111
x11 1 1 1111
x11 1 1 1111
x11 1 1 1111
xx111 11 1 1 1111
xx111 11 1 1 1111
xx111 11 1 1 1111
xxx11111 111 11 1 1 1111
xxx1 111 11 1 1 1111
xxx1 111 11 1 1 1111
xxxx1111 1 111 11 1 1 1111
xxxx 1 111 11 1 1 1111
xxxx 1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxxx1 1  1 111 11 1 1 1111
xxxxxx1 1  1 111 11 1 1 1111
xxxxxx
xxxxxx
xxxxxx
xxxxxx
111111

Answer 3

Haskell, 76 71 bytes

p x y m=[i|(p,i)<-zip(x#y)[0..],(x,y)==p]!!1where x#y=(x,y):y#mod(x+y)m

Usage example: p 1 1 5 -> 20.

How it works: # builds an infinite list of (i,i+1) pairs of the modular Fibonacci sequence. e.g. with m==5: 1#1-> [(1,1),(1,2),(2,3),(3,0)...]. The list comprehension [i| ... ] returns a list of indices of the positions of (x,y) within x#y. From this list I take the second element (-> !!1), because the first (index 0) is always at the beginning of x#y.

Edit: replaced elemIndices from Data.List with my own version.

Answer 4

Pyth, 18 17 16 15 bytes

fqQu,eG%sGvzTQ1

Example input:

6
[2, 4]

Will output 8.

It works by outputting increasingly long Fibonacci sequences (in pairs), until the end is the same as the start.

Answer 5

C, 78 72 bytes

An essentially straightforward C solution. Perhaps there is a shorter solution by considering analytic expressions for Pisano periods of generalized Fibonacci numbers, though this thesis from 2013 makes it look like such expressions are not known.

g(o,t,m,N,M,i,v){N=o;M=t;for(i=1;v=N+M,N=M,M=v%m,N-o|M-t;i++);return i;}

Readable version, by way of explanation, is

int f(int one, int two, int mod) {
  int new_one, new_two, i, tmp;
  new_one = one;
  new_two = two;
  for(i = 1;
      tmp = new_one + new_two, new_one = new_two, new_two = tmp % mod,
      new_one - one | new_two - two;
      i++);
  return i;
}

And the examples

$ ./mod_fib 1 1 5
20
$ ./mod_fib 1 1 4 
6
$ ./mod_fib 3 3 6         
3
$ ./mod_fib 2 4 6         
8

EDIT: returning the value instead of printing it is allowed in the spec and saves 6 bytes.

Answer 6

Prolog, 116 bytes

a(A,B,M,R):-f([B,A],A,B,M,1,R).
f([A,B|T],X,Y,M,Z,R):-Z=0,Y=A,X=B,length(T,R);C is(A+B)mod M,f([C,A,B|T],X,Y,M,0,R).

Example: a(1,1,5,R). outputs R = 20 .

Answer 7

CJam, 23 bytes

q~:MM*{_2$+M%}*]2ew(a#)

Reads whitspace-separated numbers from STDIN, in the same order as in the question.

Works by generating m² more numbers, pairing all and searching the index of the first pair in the rest.

Try it online in the CJam interpreter.

Answer 8

Much shorter answers have been posted, but:

EcmaScript 6, 67 64 62 56 bytes

let f=(d,e,m,a=e,b=d+e)=>a^d||b^e?f(d,e,m,b,(a+b)%m)+1:1

Examples:

f(1,1,5) //20
f(1,1,4) // 6

Answer 9

Perl, 88 bytes

($v,$w,$m)=@ARGV;$x=$v;$y=$w;do{$c++;($x,$y)=($y,($x+$y)%$m)}while($x-$v||$y-$w);print$c

Arguments given on the command line, in the order as in the question.