4
$\begingroup$


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.

  • 1
    I wouldn't be surprised if your recipe is already the optimal one, although I don't have time to think about it right now. This should have something to do with it: http://en.wikipedia.org/wiki/Stern-Brocot_tree2010-12-17
  • 0
    Ah, so it wasn't optimal after all. (Which should have been quite obvious, considering the simple counterexample given by TonyK below.)2010-12-18

3 Answers 3

3

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

  • 0
    This is also the method used by Chuquet (in the Middle ages) to approximate $k$th roots of rational numbers.2011-10-25
2

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.

1

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

  • 0
    Your link is broken.2016-07-01