Finding the simplest rational in a closed interval 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.
 A: 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.
A: 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]$.
A: 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."
