20
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Is the cycle always formed by reaching the initial values again? Or is it possible that there's a cycle that does not include the initial values? If yes, it would be good to have a test example for this case. I haven't found one with a few random attempts, but I don't have the mathematical skills to prove that the values will always go back to the initial values. \$\endgroup\$ – Reto Koradi Jul 18 '15 at 14:30
  • 3
    \$\begingroup\$ @RetoKoradi Cycles must always include initial values, because there can't be any branching. Suppose that the first number in the cycle is A_i, and let the number behind A_i in the cycle be X. A_i+1 - A_i = A_i-1, but it also equals X, so A_i-1 equals X, a contradiction. \$\endgroup\$ – lirtosiast Jul 18 '15 at 14:52
  • \$\begingroup\$ Possibly of interest: math.stackexchange.com/questions/1358310/… \$\endgroup\$ – mathmandan Jul 18 '15 at 15:52
15
\$\begingroup\$

Python, 56

g=lambda a,b,m,u=0:u!=(a,b)and-~g(b,(a+b)%m,m,u or(a,b))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's a pity that the default argument of u=0 makes it a lot harder to replace a,b with *x and (a+b) with sum(*x)... \$\endgroup\$ – Sp3000 Jul 18 '15 at 14:54
  • \$\begingroup\$ Great method for storing the initial values while iterating the current ones. \$\endgroup\$ – xnor Jul 18 '15 at 19:22
9
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is nuts. Nice work! \$\endgroup\$ – Alex A. Jul 19 '15 at 3:38
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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 .

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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 m2 more numbers, pairing all and searching the index of the first pair in the rest.

Try it online in the CJam interpreter.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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