Say I'm given two real numbers as inputs: $x$ and $y$, with $x < y$. I want to find the smallest natural number n such that there's at least one integer between $nx$ and $ny$ (inclusive of $nx$ and $ny$).
The largest $n$ can possibly be is $\lceil{\frac{1}{y-x}}\rceil$ because at that point the gap between $nx$ and $ny$ is at least $1$.
In general we should expect $x$ and $y$ to be 'very close' so checking all the possibilities is undesirable.
How can I determine $n$ efficiently?
I think $n$ will be the smallest denominator $d$ of any rational number $\frac{m}{d}$ in the range $[x,y]$. We know $n \leq d$ because multiplying a fraction $\frac{m}{d} \in [x,y]$ by $d$ will give you an integer in the range $[dx, dy]$, namely $m$. We know $n \geq d$ because if $n$ were smaller than $d$ you could construct a fraction in the range $[x,y]$ with a smaller denominator than $d$ (the fraction's denominator would be $n$ and its numerator would be the integer in range $[nx, ny]$)
So you want to find the "simplest" (smallest denominator) rational number in the range $[x,y]$. This can be done in something like $O[\log(\frac{1}{y - x})]$ time by dividing an conquering with mediants.
The mediant of $\frac{a}{b}$ and $\frac{c}{d}$ is $\frac{a + b}{c + d}$. The mediant of $\frac{a}{b}$ and $\frac{c}{d}$ will lie between $\frac{a}{b}$ and $\frac{c}{d}$, and (if $ad - bc = 1$) the mediant will be the rational in that range with the smallest possible denominator. You can use this to binary search for lowest denominator fraction in the desired range
Here's some python code to search a Stern–Brocot tree to give the answer. It starts with the range $[\frac{0}{1}, \frac{1}{1}]$ and uses the simplest fraction within that range as a pivot to binary search until it finds a fraction within $[x, y]$.
from fractions import Fraction
def simplest_fraction(x, y):
"""Finds the rational number with smallest denominator in the given range.
Range is inclusive"""
if x > y:
raise ValueError('{} > {}'.format(x, y))
if int(x) != int(y):
return 1
assert int(x) == int(y)
int_part = int(x)
x -= int_part
y -= int_part
left_frac, right_frac = Fraction(0), Fraction(1)
assert left_frac < x < y < right_frac
while left_frac < x:
determinant = (left_frac.denominator * right_frac.numerator -
(left_frac.numerator * right_frac.denominator))
assert determinant == 1, ('Mediant not guaranteed '
'to have smallest denominator in the range. '
'left: {}, right: {}, determinant: {}').format(
left_frac, right_frac, determinant)
mediant = Fraction(upper.right_frac + left_frac.numerator,
left_frac.denominator + right_frac.denominator)
if x <= mediant <= y:
return mediant + int_part
elif y < mediant:
right_frac = bisection
elif mediant < x:
left_frac = mediant
def smallest_n(x, y):
return simplest_fraction.denominator
You know that: $1\leq n\leq \big\lceil\dfrac{1}{x-y}\big\rceil$ You can create a pretty fast algorithm for finding the lowest $n$ by splitting possibilities in half repeatedly. Here's some Python code.
from math import ceil
from math import floor
def findN(x,y):
lower = 1
upper = ceil(1/(x-y))
while upper - lower >= 1:
if floor(x * floor((upper+lower)/2)) - floor(y * floor((upper+lower)/2)) >= 1:
upper = ceil((upper+lower)/2)
else:
lower = ceil((upper+lower)/2)
return upper
If the average of the lower and upper bounds is a possibillity for $n$. Then the average is the new upperbound and otherwise it's the new upperbound, until the difference between the two is no longer greater than 1. In the beginning, upper is a value for $n$ and upper only gets replaced with numbers that also work for $n$.
I just realised this won't always give you the lowest possible value of $n$, though often it does.
