Let's suppose we have a fraction and we'd like to find a "nicer" fraction slightly smaller than it --- the smaller fraction should have a smaller denominator than the original one and, subject to these conditions, should be as large as possible.

Let's take the example 19/43.

import Data.Ratio
main :: IO ()
main = print . maximum . filter (< 19%43) $ [a % b | b <- [1..42], a <- [1..b]]

Tada! The answer is 15/34.

Okay, just kidding --- this is a math blog! Approximating fractions, you know, involves continued fractions, so let's look at that.



Consider the function . It's easily seen to be monotonic by induction. Count the divisions and you'll find it's strictly increasing. As a consequence, if we decrease by one we get

This is the correct answer because it's the answer our program gave decreasing made the denominator smaller (if is a positive integer, one can verify by induction that the final numerator and denominator of the continued fraction are increasing linear functions of ) and because the continued fraction of any fraction between 15/34 and 19/43 has to start with the same coefficients:



Except what goes in the would have to be between 3 and 4, so it would not be an integer, so it would have an even larger numerator and denominator and, for the same reasons as above, would lead to a final fraction with greater final numerators and denominators. So there's nothing nicer between 19/43 and 15/34.

Of course, this only works when there's an even number of divisions. Let's look at the symmetric problem, shall we? What's the closest fraction larger than 19/43 that has a smaller denominator?

import Data.Ratio
main :: IO ()
main = print . maximum . filter (> 19%43) $ [a % b | b <- [1..42], a <- [1..b]]

The answer to this is 4/9. You can't get here by increasing above; that would move the fraction in the right direction but end up increasing the denominator too. If you consider the function instead, which is strictly decreasing in , you see that you need to decrease but make it nicer. The problem is that initially and there are no nicer fractions (with lower denominator) below . So you just have go all the way to , which is lopping off the final term 1/4.


Depending on the parity of the length of the continued fraction, you lop off the last term to go one way and decrease the term to go the other.

These are the convergents and semiconvergents of the original fraction. You can also define them by recurrence relations involving the coefficients.

(This is an underwhelming piece of math compared to the other stuff on my blog, I know.)