cp's OEIS Frontend

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

%I A066853 #26 Oct 30 2022 18:19:59
%S A066853 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,
%T A066853 21,10,30,19,21,19,13,35,15,29,13,25,30,19,18,33,20,45,21,15,15,37,50,
%U A066853 35,30,37,29,12,25,33,20,37,55,25,21,23,42,45,38,51,20,29,70,44,15,57
%N 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).
%C A066853 The Fibonacci numbers mod n for any n are periodic - see A001175 for period lengths. - _Ron Knott_, Jan 05 2005
%C A066853 a(n) = number of nonzeros in n-th row of triangle A128924. - _Reinhard Zumkeller_, Jan 16 2014
%H A066853 T. D. Noe, <a href="/A066853/b066853.txt">Table of n, a(n) for n = 1..10000</a>
%H A066853 Casey Mongoven, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from175to192.pdf">Sonification of multiple Fibonacci-related sequences</a>, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.
%e A066853 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.
%e A066853 a(11)=7 since Fibonacci numbers reduced modulo 11 are {0, 1, 2, 3, 5, 8, 10}.
%t A066853 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_ *)
%o A066853 (Haskell)
%o A066853 a066853 1 = 1
%o A066853 a066853 n = f 1 ps [] where
%o A066853    f 0 (1 : xs) ys = length ys
%o A066853    f _ (x : xs) ys = if x `elem` ys then f x xs ys else f x xs (x:ys)
%o A066853    ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
%o A066853 -- _Reinhard Zumkeller_, Jan 16 2014
%o A066853 (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
%Y A066853 Cf. A001175, A079002.
%K A066853 nonn
%O A066853 1,2
%A A066853 _Reiner Martin_, Jan 21 2002