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

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

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.

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