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,2

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.

Links

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

Example

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.

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}]

Crossrefs

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

Sequence in context: A353384 A335315 A307805 * A173817 A198383 A334268

Adjacent sequences: A189764 A189765 A189766 * A189768 A189769 A189770

Keyword

nonn

Author

T. D. Noe, May 10 2011

Status

approved