How to find a "simple" fraction between two other fractions?

Question

If we have two fractions $a = { a_1 \over a_2} $ and $c = {c_1 \over c_2}$ with $a<c$,

how to find the fraction

$b = { b_1 \over b_2 }$ , $a < b < c$

for which some measure of simpleness like

$b_1^2+b_2^2$

is minimal, without trying every possible fraction?

Answer 1

I'll suppose both fractions are positive; if their signs differ take $\frac01$ as intermediate fraction and both negative is similar to both positive. The absolutely simplest fraction in the interval $(a,c)$ (in the sense that both its numerator and its denominator are the smallest possible in the interval, so it doesn't much matter how you weigh each of them) is found in terms of the position of $a$ and $b$ in the Stern-Brocot tree. Let $d$ be the closest common ancestor of $a$ and $c$ (I'll consider $0$ to be the root of the tree, so in case $a=0$ one gets $d=0$). If $d\notin\{a,c\}$ then $d$ is the simplest fraction between $a$ and $c$; it is in fact like all positive fractions the simplest fraction in all the open interval between its left and right "direct ancestors" in the tree; here the parent of a fraction $\alpha$ is one direct ancestor of $\alpha$, and its other direct ancestor is found by going up from the parent to the first ancestor which is in the opposite direction as the parent was from $\alpha$ (for positive integers the right parent is taken to be $\infty$). This interval contains both $a$ (as a left descendant of $d$) and $c$ (a right descendent of $d$).

The situation is somewhat more complicated if $d\in\{a,c\}$, in other words if one of the fractions is an ancestor of the other (since you question forbids taking $b=a$ or $b=c$). Set $\{d,e\}=\{a,c\}$, so $e$ is the one of $a,c$ that is unequal to $d$. If $d$ is not one of the two direct ancestors of $e$, then some fraction on the path from $d$ to $e$ in the tree lies in the interval $(a,c)$, and the first such fraction gives your $b$. It is in fact found by taking one step down from $d$ in the direction of $e$, then zero or more steps in the opposite direction, stopping just before the next step that would again be in the direction from $d$ to $e$.

Finally there remains the case that $d$ is one of the two direct ancestors of $e$. This is the only case where one needs to go below $e$ in the tree; in fact one step down from $e$ in the direction of $d$ (left or right, but not up of course) will give the fraction $b$ sought. In fact $b=\frac{a_1+c_1}{a_2+c_2}$ in this case.

Here are examples of the three cases:

• $a=\frac47$, $c=\frac34$, $d=\frac23= b$ the closest common ancestor
• $a=\frac34$, $c=\frac{58}{75}$, $d=a=\frac34$ is an ancestor of $c=\frac{58}{75}=e$ but not one of its direct ancestors $(\frac{17}{22},\frac{41}{53})$; one finds $b$ by descending $\frac34$ left $\frac45$ right $\frac79$ right $\frac{10}{13}=b$ left ...
• $a=\frac34$, $c=\frac{10}{13}$, now $d=a$ is a direct ancestor of $c=e$, so one needs to descend from $e$ to the left (since $d\lt e$) giving $b=\frac{13}{17}=\frac{3+10}{4+13}$

Descending in the Stern-Brocot tree is easy if one knows the direct ancestors of the current fraction: add to numerator and denominator separately the numerator respectively denominator of the direct ancestor in the direction one is going to. Going up is harder (since it is not reasonable to suppose one knows the direct ancestors in this case), but performing the Euclidean algorithm to the pair (numerator,denominator) using subtractions, keeping track of the side from which the subtraction is performed, will give the successive directions to take from the top at $\frac11$ down to find the given fraction in the tree; this reveals all its ancestors. For instance for $\frac{58}{75}$ the Euclidean algorithm steps $(58,75)$ left $(58,17)$ right $(41,17)$ right $(24,17)$ right $(7,17)$ left $(7,10)$ left $(7,3)$ right $(4,3)$ right $(1,3)$ left $(2,1)$ left $(1,1)$ tell you that you can find $\frac{58}{75}$ by descending in the tree by $\frac11$ left $\frac12$ right $\frac23$ right $\frac34$ right $\frac45$ left $\frac79$ left $\frac{10}{13}$ right $\frac{17}{22}$ right $\frac{24}{31}$ left $\frac{41}{53}$ left $\frac{58}{75}$.

To find the closest common ancestor between two fractions, apply this Euclidean algorithm in parallel for the two, up to the first point where the two require operations in different directions; descending from $\frac11$ to that point reveals the closest common ancestor. For instance for the first example, the fractions are $\frac47$ and $\frac34$, so one performs in parallel

• $(4,7)$ left $(4,3)$ right $(1,3)$ left $(1,2)$
• $(3,4)$ left $(3,1)$ right $(2,1)$ right $(1,1)$

The common path is left,right then they diverge, so one performs $\frac11$ left $\frac12$ right $\frac23=d$ to find the closest common ancestor $d$.

Answer 2

A fairly simple procedure is to expand both $a_1/a_2$ and $b_1/b_2$ as continued fractions, and then take the part of the continued fraction expansion that agree between them, and put a terminating denominator that is one more than the smallest of the two first disagreeing elements. (*)

Then convert the resulting continued fraction back to an ordinary fraction. The result ought to be (if I remember correctly) the fraction in $(\frac{a_1}{a_2},\frac{b_1}{b_2})$ that has the smallest denominator.

*) with some special cases if the disagreement comes right at the end of one or both of the continued fractions.

Answer 3

Just sticking to positive integers and with fractions in lowest terms,

I think you only need to check each possible $b_2$ up to $\max(a_2,c_2)$ whether $\lfloor (b_2 a_1+a_2)/a_2 \rfloor \times c_2 \lt b_2 \times c_1$ and if so $b_1 = \lfloor (b_2 a_1+a_2)/a_2 \rfloor$.

If not then the theory underlying Stern-Brocot trees suggests to me you will need the mediant with $b_1=a_1+c_1$ and $b_2=a_2+c_2$.

Answer 4

Here's a simple and efficient algorithm, expressed explicitly in Python. It resembles the Euclidean algorithm for computing greatest common divisors, and it can be derived from the descriptions in other answers in terms of continued fractions and/or the Stern-Brocot tree, but it's also straightforward to give a proof of correctness that doesn't use those concepts directly. We'll give the code first, and then sketch that proof of correctness.

Here's the code:

def simplest_in_interval(r, s, u, v):
    """
    Find simplest fraction in an open subinterval of the positive reals.
    
    Given nonnegative integers r, s, u and v with r*v < s*u, return a pair
    x, y of relatively prime positive integers such that x/y is the
    simplest fraction in the open interval (r/s, u/v) (in the case v > 0),
    or the simplest fraction in the interval (r/s, ∞) (in the case v = 0).
    """
    a, b, c, d = 1, 0, 0, 1
    while s <= r or u <= v:
        q = r // s
        r, u, b, d = r - q * s, u - q * v, b + q * a, d + q * c
        q = v // u
        s, v, a, c = s - q * r, v - q * u, a + q * b, c + q * d
    return a + b, c + d

A note for non-Python-speakers: the // operator in Python performs floor division; that is, a // b gives the value of $\lfloor a/b\rfloor$.

Here's an example of the above function in action: finding the simplest fraction in the interval (314/100, 315/100). (Note that there's no requirement for the input fractions to be given in lowest terms.)

>>> simplest_in_interval(314, 100, 315, 100)
(22, 7)

Sketch of proof of correctness.

Write $J$ for the originally-specified open interval $(r/s, u/v)$. As the algorithm progresses, we maintain eight separate integer-valued variables: $a$, $b$, $c$, $d$, $r$, $s$, $u$ and $v$. Now at every stage of the algorithm, the following loop invariants hold:

• $b$, $c$, $r$ and $v$ are nonnegative
• $a$, $d$, $s$ and $u$ are positive
• $rv < su$ (in fact, $su - rv$ stays constant), so $r$, $s$, $u$ and $v$ determine an open subinterval $K = (r/s, u/v)$ of the positive real line (where as a special case we allow $v=0$ to represent a right endpoint of $\infty$)
• $ad - bc = 1$, and $a$, $b$, $c$ and $d$ describe a bilinear transformation $T: x \mapsto (ax + b) / (cx + d)$
• $T$ maps $K$ bijectively (and monotonically) to the original interval $J$, so establishes an order-preserving bijection between the rationals in $K$ and those in $J$

The above invariants can be established in the usual way, by checking that they're true just before the while loop is entered for the first time (at which point $K = J$ and $T$ is the identity map), and then by checking that if they're true at the start of any given iteration of the loop body, then they're also true at the end of the loop body for that iteration.

When the while loop exits, we must have $r < s$ and $v < u$, or in other words, $r/s < 1 < u/v$. So at that point the interval $K$ contains $1$. Now every fraction in the original interval $J$ has the form $(ap + bq) / (cp + dq)$ for some $p/q$ in $K$, and assuming that $p/q$ is written in lowest terms, it follows from the fact that $ad-bc = 1$ that $(ap + bq) / (cp + dq)$ is also written in lowest terms. Since $a$, $b$, $c$ and $d$ are all nonnegative, the simplest possible fraction arises when $p$ and $q$ are minimal - that is, when $p = q = 1$, and that simplest fraction is $(a + b) / (c + d)$.

There's one final thing we need to know, and that's that the while loop does exit - that is, that the while loop condition eventually becomes false, and that we don't simply enter an infinite loop. For this, it's enough to observe that on every iteration of the loop, either $r$ or $v$ decreases, and neither ever increases. Since both $r$ and $v$ stay nonnegative, we can't continue those decreases indefinitely, so the loop must terminate after finitely many iterations. This completes the sketch of the proof.