login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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)=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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 04:30 EDT 2020. Contains 335459 sequences. (Running on oeis4.)