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,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 n-th 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 Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.

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] (* Jean-Franç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[#v-1]!=0, listput(v, (v[#v]+v[#v-1])%n)); #Set(v) \\ Charles R Greathouse IV, Jun 19 2017

Crossrefs

Cf. A001175, A079002.

Sequence in context: A373227 A331303 A161658 * A264856 A141258 A117656

Adjacent sequences: A066850 A066851 A066852 * A066854 A066855 A066856

Keyword

nonn

Author

Reiner Martin, Jan 21 2002

Status

approved