A189767 Least number k such that the set of numbers {Fibonacci(i) mod n, i=0..k-1} contains all possible residues of Fibonacci(i) mod n.

1, 2, 4, 5, 10, 10, 13, 11, 17, 22, 9, 23, 19, 37, 20, 23, 25, 19, 17, 53, 15, 25, 37, 23, 50, 61, 53, 45, 13, 58, 29, 47, 39, 25, 77, 23, 55, 17, 47, 59, 31, 37, 65, 29, 93, 37, 25, 23, 81, 148, 67, 75, 77, 53, 19, 45, 71, 37, 57, 119, 43, 29, 45, 95, 103

Offset: 1

Author

T. D. Noe, May 10 2011

Keywords

• nonn

Comments

Sequence A066853 gives the number of possible residues of the sequence Fibonacci(i) mod n for i=0,1,2,.... Here we compute the smallest k required to find all A066853(n) residues in the first k terms (starting at i=0) of Fibonacci sequence (mod n). We know that k is at most A001175(n), the period of Fibonacci(i) mod n. It appears that when n is a prime in A053032, then a(n)=n-1.

Examples

			Consider n=8. The Fibonacci numbers mod 8 have period 12: 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1. The set of residues is {0, 1, 2, 3, 5, 7}. How long does it take to find all 6 residues in the sequence Fibonacci(i) mod n? The answer is 11 because 7 finally appears as Fibonacci(10) mod 8.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000045 (Fibonacci numbers), A001175, A053032, A066853, A189768 (residues).

Programs

Maple

F:= proc(n)
 local r, k, a,ap, t, V;
ap:= 0: a:= 1; r:= 1;
V:= Array(0..n-1);
V[0]:= 1;
V[1]:= 1;
for k from 2 do
     t:= a + ap mod n;
     ap:= a;
     a:= t;
     if ap = 0 and a = 1 then return r +1 fi;
     if V[t] = 0 then
        r:=k;
        V[t]:= 1;
     fi
od:
end proc:
F(1):= 1:
seq(F(n),n=1..100); # Robert Israel, Dec 23 2015

Mathematica

pisano[n_] := Module[{a={1,0},a0,k=0,s}, If[n==1, 1, a0=a; While[k++; s=Mod[Total[a],n]; a[[1]]=a[[2]]; a[[2]]=s; a != a0]; k]]; Table[p=pisano[n]; f=Mod[Fibonacci[Range[0,p]],n]; u=Union[f]; k=1; While[Union[Take[f,k]] != u, k++]; k, {n,100}]