Elementary Number Theory – How to Find a Simple Fraction Between Two Fractions

algorithmselementary-number-theoryfractions

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?

Best Answer

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

Related Question