Finding the simplest rational in a closed interval

Question

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.

Answer 1

If $p$ and $q$ are integers such that $a \leq \frac pq \leq b,$ then $qa \leq p \leq qb.$ In fact, since $p$ is an integer, $\lceil qa \rceil \leq p \leq \lfloor qb \rfloor.$

For any integer $q,$ then, if $\lceil qa \rceil > \lfloor qb \rfloor$ then it is impossible to write $\lceil qa \rceil \leq p \leq \lfloor qb \rfloor$ for any integer $p$ and therefore there is no rational number with denominator $q$ in the interval $[a,b].$

On the other hand, suppose we find an integer $q$ such that $\lceil qa \rceil \leq \lfloor qb \rfloor.$ We can set $p = \lceil qa \rceil,$ and we then have $a \leq \frac pq \leq b.$

This suggests a brute-force algorithm: set $q$ initially to $1.$ If $\lceil qa \rceil > \lfloor qb \rfloor$ then set $q$ to the next higher integer and compare $\lceil qa \rceil$ and $\lfloor qb \rfloor$ again. Repeat until a value $q$ is found such that $\lceil qa \rceil \leq \lfloor qb \rfloor.$ Since all smaller integers were tried as denominators and failed, the value $q$ found in this way is the smallest possible denominator of a rational number in the interval $[a,b].$ As before, set $p = \lceil qa \rceil$ in order to obtain $a \leq \frac pq \leq b.$

This description glosses over some possible difficulties, such as how to evaluate $\lceil qa \rceil$ (for example) if $a$ is irrational. It would be nice to have a better algorithm, in particular one that wasn't essentially "try every possible value until you find one that works."

Answer 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]$.

Answer 3

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.