

A189767


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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)=n1.


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..n1);
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: A276608 A173660 A307805 * A173817 A198383 A334268
Adjacent sequences: A189764 A189765 A189766 * A189768 A189769 A189770


KEYWORD

nonn


AUTHOR

T. D. Noe, May 10 2011


STATUS

approved



