1
$\begingroup$

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.

$\endgroup$

closed as off-topic by user21820, Namaste, Xander Henderson, Mostafa Ayaz, Parcly Taxel Jul 22 '18 at 17:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Namaste, Xander Henderson, Mostafa Ayaz, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – Brent Baccala Nov 24 '14 at 22:20
  • $\begingroup$ the following chapter on rational approximation might be useful ams.org/bookstore/pspdf/mbk-48-prev.pdf $\endgroup$ – Mirko Nov 24 '14 at 22:34
  • $\begingroup$ 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. $\endgroup$ – Scot Nov 24 '14 at 22:46
  • $\begingroup$ Thanks for the reference Mirko. I saw the chapter on rational approximations about an hour ago. It certainly looks relevant to the problem. $\endgroup$ – Scot Nov 24 '14 at 22:50
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jul 20 '18 at 0:39
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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."

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.