Re: Fibonacci Question

Pubkeybreaker <pubkeybreaker@xxxxxxx> writes:

An interesting question posed on the Mersenne Forum (not my question)
is:

What is the range of F_n mod F_m for Fibonacci numbers F_n, F_m as
(m,n) varies
over all positive integer pairs? Is the range all of Z? If, not,
what is the density (in Z)
of this set. ? (this latter question is mine)

I assume you're talking about the positive integers, not Z, and
"F_n mod F_m" as meaning the integer k with 0 <= k < F_m and
F_n == k mod F_m. Otherwise e.g. every integer is congruent to
F_n mod F_1.

Note that if n = q m + r with 0 <= r < m, F_n == F_{m-1}^q F_r mod F_m.
So for any given m, there are fewer than n^2 different values for
F_n mod F_m. If we pretend these are distributed randomly in
{0,1,2,...,F_m - 1}, then the expected number of times a given
positive integer k can be written as F_n mod F_m would be less than
sum_{m: F_m > k} m^2/F_m, which unless I've made a mistake is asymptotic to
ln(k)^2/(ln(p)^3 k) where p = (sqrt(5)+1)/2. In particular it goes to 0
as k -> infinity. So the asymptotic density ought to be 0. Of course,
this is just heuristic, not a proof.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: Fibonacci Question
    ... On May 17, 6:05 pm, Robert Israel ... over all positive integer pairs? ... positive integer k can be written as F_n mod F_m would be less than ...
    (sci.math)
  • Re: Fibonacci Question
    ... over all positive integer pairs? ... positive integer k can be written as F_n mod F_m would be less than ... So the asymptotic density ought to be 0. ...
    (sci.math)
  • Re: Fibonacci Question
    ... Robert Israel wrote: ... over all positive integer pairs? ... positive integer k can be written as F_n mod F_m would be less than ...
    (sci.math)
  • Re: Given x,y find smallest n: 2^n=1 mod (xy).
    ... Pubkeybreaker writes: ... How can I find the least positive integer n, ... so that 2^n is congruent to 1 modulus xy, ...
    (sci.math)
Quantcast