Minimal $ab$ for Rational Number $a/b$ in an Interval
Given rational numbers $L$ and $U$, $0<L<U<1$, find rational number $M=a/b$ such that $L \le M<U$ and $(a\times b)$ is as small as possible---$a$ and $b$ are integers. For example,
- If $L=66/101$ and $U=19/29$ then $M=17/26$.
- If $L=66/101$ and $U=19/28$ then $M=2/3$.
Right now I'm using a naive search that is exponential in complexity. Is there a better method?
If it is of any help, it can be assumed the prime factorization of numerator and denominator of $U$ and $L$ are known.
As per TonyK's answer, it is only necessary to find the smallest denominator for which a fraction in $[L,U)$ exists. To avoid what he calls "messy" oscillations, we can proceed as follows:
- Start with $(a,b,c,d)=(0,1,1,1)$.
- *[Remark: We have $\frac ab<L<U\le \frac cd$, and $ad-bc=-1$, and any fraction between $\frac ab$ and $\frac cd$ has denominator $\ge b+d$]*$\quad$ Let $u\leftarrow a+c$, $v\leftarrow b+d$.
- If $u<Lv$, let $a\leftarrow u$, $b\leftarrow v$ and go to step 2
- If $u\ge Uv$, let $c\leftarrow u$, $d\leftarrow v$ and go to step 2.
- We have found $M=\frac uv$ for which the product $uv$ is minimal. Terminate
It is enough to find the smallest possible $b$, and then the smallest possible $a$ given $b$. This is not completely obvious, so I will try to prove it:
Suppose we have positive integers $a,b$ such that
(i) $b$ is the smallest denominator of all fractions in $[L,U)$; and
(ii) $a/b$ is the smallest multiple of $1/b$ in $[L,U)$.
This means that $(a-1)/b < L \le a/b$, and so $a-1<bL\le a$.
Now suppose for the sake of contradiction that we have found positive integers $c,d$ such that $c/d \in [L,U)$ and $cd < ab$. Then $b < d$, by (i), so $bL < dL$. (The case $b=d$ is ruled out, because then we would have $c \ge a$, by (ii), and hence $cd \ge ab$.)
But now we have $a-1 < bL < dL \le c$, because $c/d \ge L$.
Hence $a < c$, which together with $b < d$ gives us $ab < cd$, contradicting our assumption.
And to find the smallest denominator in an interval $[L,U)$, it is enough to compute the continued fractions of $L$ and $U$, and truncate them at the first position where they differ. Your examples:
$66/101 = [0;1,1,1,7,1,3]$
$19/29 = [0;1,1,1,9]$
So the answer is $[0;1,1,1,8] = 17/26$
$66/101 = [0;1,1,1,7,1,3]$
$19/28 = [0;1,2,9]$
So the answer is $[0;1,2] = 2/3$
Actually it's not quite as simple as that, because continued fractions oscillate about their convergent, rather than converging monotonically. But you can google "continued fractions" to get the messy details.