You may also like

problem icon

BT.. Eat Your Heart Out

If the last four digits of my phone number are placed in front of the remaining three you get one more than twice my number! What is it?

problem icon

Approximations, Euclid's Algorithm & Continued Fractions

This article sets some puzzles and describes how Euclid's algorithm and continued fractions are related.

problem icon

Euclid's Algorithm II

We continue the discussion given in Euclid's Algorithm I, and here we shall discover when an equation of the form ax+by=c has no solutions, and when it has infinitely many solutions.

Euclid's Algorithm and Musical Intervals

Stage: 5 Challenge Level: Challenge Level:2 Challenge Level:2

Here is another beautifully explained solution from Andrei of Tudor Vianu National College, Bucharest, Romania:


$$ \left({5\over 4}\right)^m = \left({2\over 1}\right)^n .$$ This can be written equivalently: $$m\log {5\over 4} = n \log 2$$ or $${m\over n} = {\log 2 \over \log 5 - log 4} = 3.10628372 \quad (1).$$ Now, I shall use Euclid's algorithm to find the first 4 rational approximations of: $${\log 2 \over \log 5 - log 4}.$$ For the first approximation, I write: $$3.10628372 = 3 + {1\over {1\over 0.10628372}} \approx 3 + {1\over 9.408778692}\quad (2).$$ So, the first approximation is $${m\over n} \approx 3 + {1\over 9} = {28\over 9} = 3.111111111....$$ Now, for the second approximation I have: $$3 + {1 \over \displaystyle 9 + {1\over \displaystyle {1\over \displaystyle 0.408778692}}} = 3 + {1 \over \displaystyle 9 + {1\over \displaystyle 2.446311463}}$$ The second approximation for $m/n$ is: $${m\over n} \approx 3 + {1\over {9 + {1 \over \displaystyle 2}}} = {59\over 19} \approx 3.105263158.$$ For the third approximation, I obtain: $$3 + {1 \over \displaystyle 9 + {1\over \displaystyle 2 + {1\over \displaystyle {1\over \displaystyle 0.446311463}}}} = 3 + {1 \over \displaystyle 9 + {1\over \displaystyle 2 + {1\over \displaystyle 2.240587757}}}.$$ and consequently $${m\over n} \approx 3 + {1\over \displaystyle 9 + {1\over \displaystyle 2 + {1\over \displaystyle 2}}} = 3 + {1\over \displaystyle 9 + {2\over \displaystyle 5}}= {146\over 47} \approx 3.106382979.$$ Then the fourth approximation for m/n is: $${m\over n} \approx 3 + {1 \over \displaystyle 9 + {1\over \displaystyle 2 + {1\over \displaystyle 2 + {1\over \displaystyle 4}}}} = {643\over 207} \approx 3.106280193.$$ I see that using continued fractions I come nearer to the given real number by rational numbers greater and smaller than the number: the first and third approximations are greater than $m/n$ and the second and the fourth are smaller than the initial number.

This is a natural thing. I arrived to the first approximation considering, in relation (2) a smaller denominator: $${m\over n}\approx 3 + {1\over 9.408778692} < 3 + {1\over 9} = {28\over 9}.$$ Now, I shall do the same thing for the second approximation: $${m\over n} \approx 3 + {1\over 9 + {1\over \displaystyle 2.446311463}} > 3 + {1\over 9 + {1\over \displaystyle 2}}.$$ So, the second approximation is smaller than the initial number.

In a similar manner, the odd-order approximations are greater than $m/n$, but they form a decreasing series. The even-order approximations are smaller than $m/n$, and they form an increasing series.