Finding the simplest rational in a closed interval [closed]

Given a closed interval [a,b], how would you find the "simplest rational", p/q, contained in that interval. By simplest, I mean the rational with the smallest denominator q. You may, if you wish assume that the interval is very small. We can already construct a rational contained in the interval, but in general our constructed rational does not have the smallest q. Thank You.

Solution 1:

I think you can solve it with a Farey fraction algorithm.

Let's assume we start with $0\lt a\lt b\lt 1$. Any time you have

$${p\over q}\lt a\lt b\lt {r\over s}$$

with $p/q$ and $r/s$ in reduced form, you can check if

$$a\le{p+r\over q+s}\le b$$

If so, you're done. If not, replace the appropriate upper or lower bound and continue. By starting with $p/q=0/1$ and $r/s=1/1$, the Farey fraction procedure generates all rational numbers; by zeroing in on the interval $(a,b)$, the algorithm will first produce the fraction with minimal denominator.

Solution 2:

We may assume $0 < a < b$. (If $a \le 0 \le b$, then $0/1$ is the solution; and if $a < b < 0$, then solve for $[-b,-a]$.)

Let the continued fractions of $a$ and $b$ be $[a_0;a_1,a_2,...]$ and $[b_0;b_1,b_2,...]$. Let $n$ be the first position in which they differ: that is, $a_i = b_i$ for $i < n$, and $a_n \ne b_n$.

Let $c = \min(a_n,b_n)$. Then the simplest rational in $[a,b]$ is $[a_0;a_1,a_2,...,a_{n-1},c]$ if this number is in $[a,b]$; otherwise it is $[a_0;a_1,a_2,...,a_{n-1},c+1]$.