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

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

Offset: 1

Author

Reiner Martin, Jan 21 2002

Keywords

• nonn

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 n-th row of triangle A128924. - Reinhard Zumkeller, Jan 16 2014

Examples

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

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.

Crossrefs

Cf. A001175, A079002.

Programs

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

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] (* Jean-François Alcover, Feb 15 2018, after Charles R Greathouse IV *)

PARI

a(n)=if(n<8, return(n)); my(v=List([1,2])); while(v[#v]!=1 || v[#v-1]!=0, listput(v, (v[#v]+v[#v-1])%n)); #Set(v) \\ Charles R Greathouse IV, Jun 19 2017