login
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

%I #26 Oct 30 2022 18:19:59

%S 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 21,10,30,19,21,19,13,35,15,29,13,25,30,19,18,33,20,45,21,15,15,37,50,

%U 35,30,37,29,12,25,33,20,37,55,25,21,23,42,45,38,51,20,29,70,44,15,57

%N 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 The Fibonacci numbers mod n for any n are periodic - see A001175 for period lengths. - _Ron Knott_, Jan 05 2005

%C a(n) = number of nonzeros in n-th row of triangle A128924. - _Reinhard Zumkeller_, Jan 16 2014

%H T. D. Noe, <a href="/A066853/b066853.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 a(11)=7 since Fibonacci numbers reduced modulo 11 are {0, 1, 2, 3, 5, 8, 10}.

%t 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 (Haskell)

%o a066853 1 = 1

%o a066853 n = f 1 ps [] where

%o f 0 (1 : xs) ys = length ys

%o f _ (x : xs) ys = if x `elem` ys then f x xs ys else f x xs (x:ys)

%o ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps

%o -- _Reinhard Zumkeller_, Jan 16 2014

%o (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 Cf. A001175, A079002.

%K nonn

%O 1,2

%A _Reiner Martin_, Jan 21 2002