2

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.

Scot
  • 37
  • How do we specify the endpoints? Are they rational numbers? If so, then an algorithm could probably be constructed to do what you want. If not, then it's murkier. – Brent Baccala Nov 24 '14 at 22:20
  • the following chapter on rational approximation might be useful http://www.ams.org/bookstore/pspdf/mbk-48-prev.pdf – Mirko Nov 24 '14 at 22:34
  • OK. Lets suppose that the endpoints are rational and that the interval is contained in [0,1]. Further suppose the interval width is N/M, then I think you could brute force search all p/q with q<=M. That algorithm is O(M^2). Is that the best that can be done? Suppose instead that you have a very small interval and that you have continued fraction representations for both end-points. I would think that this would greatly reduce the number rationals that the algorithm would have to look at. But I still don't quite see the algorithm. – Scot Nov 24 '14 at 22:46
  • Thanks for the reference Mirko. I saw the chapter on rational approximations about an hour ago. It certainly looks relevant to the problem. – Scot Nov 24 '14 at 22:50
  • If you're still here, Scot, maybe you'd like to "accept" one of the answers you've been given by clicking in the little check mark next to it. – Gerry Myerson Jul 20 '18 at 00:39

3 Answers3

7

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.

Barry Cipra
  • 79,832
4

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

TonyK
  • 64,559
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."

David K
  • 98,388