|
|
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
|
|
LINKS
|
|
|
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
(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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|