Computing a rational number between two others, minimizing numerator and denominator

Question

Given two positive rational number $\frac{a_1}{b_1}$ and $\frac{a_3}{b_3}$ (written in lowest terms) such that $$\frac{a_1}{b_1} < \frac{a_3}{b_3},$$ I want to find a rational number $\frac{a_2}{b_2}$ such that $$\frac{a_1}{b_1} < \frac{a_2}{b_2} < \frac{a_3}{b_3}$$ and $a_2$ and $b_2$ are the smallest possible numbers

I've come with the solution $a_2 = a_1 + a_3$ and $b_2 = b_1 + b_3$ then dividing $a_2$ and $b_2$ by their greatest common divisor but there must be better solution.

Thanks by advance for your suggestions.

Answer 1

See Wikipedia's article on the mediant, which explains when your solution is the best.

Answer 2

HINT $\rm\displaystyle\quad \frac{A}B < \frac{X}Y < \frac{C}D\ \iff\ X = \frac{MA+NC}{BC-AD},\ Y = \frac{MB+ND}{BC-AD}\quad$ for some integers $\rm\:M,N>0$

This has a nice geometric interpretation in terms of plane lattices - which provides a vivid geometric interpretation of good approximations by Farey mediant searching - see my post here

Answer 3

Your solution is not the best. (Take, for instance, 1/2 and 9/10.) One way to solve your problem is to calculate the continued fractions of the two numbers until they differ. Say the continued fractions start $[x_0;x_1,x_2,x_3]$ and $[x_0;x_1,x_2,y_3]$, with $x_3 \ne y_3$. Then you can just try all values $z_3$ between $x_3$ and $y_3$ inclusive to get your answer. There might be a cleverer way to find the best $z_3$, but this way should work: it relies on the fact that continued-fraction convergents are alternately greater and less than the value that they are approximating, so one of $[x_0;x_1,x_2,x_3]$ and $[x_0;x_1,x_2,y_3]$ will lie between $a1/b1$ and $a3/b3$.
There is a slight complication: suppose $x_3$ and $y_3$ differ by one, and one of the convergents is exact. Then you might not be able to find $z_3$ such that $[x_0;x_1,x_2,z_3]$ is strictly between $a1/b1$ and $a3/b3$. But in this case you can use your formula on the two convergents (instead of on $a1/b1$ and $a3/b3$) to get the answer, because the condition that $x_3$ and $y_3$ differ by one is sufficient to guarantee that your mediant is the best approximation.
For example, 1/2=[0;2] and 9/10=[0;1,9]. So they differ at $x_1$, which means we should try [0;1] = 1 and [0;2] = 1/2. Neither is satisfactory, so we take their mediant, which is 2/3.