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.

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.
