cp's OEIS Frontend

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.

%I A189767 #12 Dec 23 2015 02:57:33
%S A189767 1,2,4,5,10,10,13,11,17,22,9,23,19,37,20,23,25,19,17,53,15,25,37,23,
%T A189767 50,61,53,45,13,58,29,47,39,25,77,23,55,17,47,59,31,37,65,29,93,37,25,
%U A189767 23,81,148,67,75,77,53,19,45,71,37,57,119,43,29,45,95,103
%N 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.
%C A189767 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.
%H A189767 T. D. Noe, <a href="/A189767/b189767.txt">Table of n, a(n) for n = 1..1000</a>
%e A189767 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.
%p A189767 F:= proc(n)
%p A189767  local r, k, a,ap, t, V;
%p A189767 ap:= 0: a:= 1; r:= 1;
%p A189767 V:= Array(0..n-1);
%p A189767 V[0]:= 1;
%p A189767 V[1]:= 1;
%p A189767 for k from 2 do
%p A189767      t:= a + ap mod n;
%p A189767      ap:= a;
%p A189767      a:= t;
%p A189767      if ap = 0 and a = 1 then return r +1 fi;
%p A189767      if V[t] = 0 then
%p A189767         r:=k;
%p A189767         V[t]:= 1;
%p A189767      fi
%p A189767 od:
%p A189767 end proc:
%p A189767 F(1):= 1:
%p A189767 seq(F(n),n=1..100); # _Robert Israel_, Dec 23 2015
%t A189767 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}]
%Y A189767 Cf. A000045 (Fibonacci numbers), A001175, A053032, A066853, A189768 (residues).
%K A189767 nonn
%O A189767 1,2
%A A189767 _T. D. Noe_, May 10 2011