Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


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.

share|improve this question
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: en.wikipedia.org/wiki/Stern-Brocot_tree –  Hans Lundmark Dec 17 '10 at 13:59
    
Ah, so it wasn't optimal after all. (Which should have been quite obvious, considering the simple counterexample given by TonyK below.) –  Hans Lundmark Dec 18 '10 at 12:35

3 Answers 3

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

share|improve this answer
    
Just so you know, I fixed the broken link in your answer. –  Mike Spivey Dec 17 '10 at 16:03
    
@Mike: thanks . –  lhf Dec 17 '10 at 17:03
    
This is also the method used by Chuquet (in the Middle ages) to approximate $k$th roots of rational numbers. –  A Walker Oct 25 '11 at 20:22

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.