

A066853


Number of different remainders (or residues) for the Fibonacci numbers (A000045) when divided by n (i.e., the size of the set of F(i) mod n over all i).


13



1, 2, 3, 4, 5, 6, 7, 6, 9, 10, 7, 11, 9, 14, 15, 11, 13, 11, 12, 20, 9, 14, 19, 13, 25, 18, 27, 21, 10, 30, 19, 21, 19, 13, 35, 15, 29, 13, 25, 30, 19, 18, 33, 20, 45, 21, 15, 15, 37, 50, 35, 30, 37, 29, 12, 25, 33, 20, 37, 55, 25, 21, 23, 42, 45, 38, 51, 20, 29, 70, 44, 15, 57
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The Fibonacci numbers mod n for any n are periodic  see A001175 for period lengths.  Ron Knott, Jan 05 2005
a(n) = number of nonzeros in nth row of triangle A128924.  Reinhard Zumkeller, Jan 16 2014


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
Casey Mongoven, Sonification of multiple Fibonaccirelated sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175192.


EXAMPLE

a(8)=6 since the Fibonacci numbers, 0,1,1,2,3,5,8,13,21,34,55,89,144,... when divided by 8 have remainders 0,1,1,2,3,5,0,5,5,2,7,1 (repeatedly) which only contains the remainders 0,1,2,3,5 and 7, i.e., 6 remainders, so a(8)=6.
a(11)=7 since Fibonacci numbers reduced modulo 11 are {0, 1, 2, 3, 5, 8, 10}.


MATHEMATICA

a[n_] := Module[{v = {1, 2}}, If[n<8, n, While[v[[1]] != 1  v[[2]] != 0, AppendTo[v, Mod[v[[1]] + v[[2]], n]]]; v // Union // Length]]; Array[a, 100] (* JeanFrançois Alcover, Feb 15 2018, after Charles R Greathouse IV *)


PROG

(Haskell)
a066853 1 = 1
a066853 n = f 1 ps [] where
f 0 (1 : xs) ys = length ys
f _ (x : xs) ys = if x `elem` ys then f x xs ys else f x xs (x:ys)
ps = 1 : 1 : zipWith (\u v > (u + v) `mod` n) (tail ps) ps
 Reinhard Zumkeller, Jan 16 2014
(PARI) a(n)=if(n<8, return(n)); my(v=List([1, 2])); while(v[#v]!=1  v[#v1]!=0, listput(v, (v[#v]+v[#v1])%n)); #Set(v) \\ Charles R Greathouse IV, Jun 19 2017


CROSSREFS

Cf. A001175, A079002.
Sequence in context: A337642 A331303 A161658 * A264856 A141258 A117656
Adjacent sequences: A066850 A066851 A066852 * A066854 A066855 A066856


KEYWORD

nonn


AUTHOR

Reiner Martin (reinermartin(AT)hotmail.com), Jan 21 2002


STATUS

approved



