Find the smallest $n$ such that an integer lies between $nx$ and $ny$ for real numbers $x$ & $y$. Say I'm given two real numbers as inputs: $x$ and $y$, with $x &lt; 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 &gt; y:
        raise ValueError('{} &gt; {}'.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 &lt; x &lt; y &lt; right_frac
    while left_frac &lt; 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 &lt;= mediant &lt;= y:
            return mediant + int_part
        elif y &lt; mediant:
            right_frac = bisection
        elif mediant &lt; 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 &gt;= 1:
        if floor(x * floor((upper+lower)/2)) - floor(y * floor((upper+lower)/2))     &gt;= 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.