Count the Fractions.

This is the first in a series of posts about sequences of fractions, circles, trees of fractions, binary search trees and ways of representing rational numbers as paths through these trees . The idea is to enjoy a bit of recreational mathematics and to use Haskell to express some of the notions in its own succinct way.

One Lot Of Fractions

First we’ll look at all unique and simplified fractions between 0 and 1 with a denominator no larger than a given value. For example, with a maximum denominator of 3, 4 and then 5 we have

    \begin{align*} \(fracs(3) = \frac{1}{3}, \frac{1}{2}, \frac{2}{3} \\ \\ \(fracs(4) = \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}\\ \\ \(fracs(5) = \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}\\ \\ \end{align*}

For completeness and a pleasing symmetry we can regard each sequence as starting with \frac{0}{1} and ending with \frac{1}{1}. Such a sequences are known as the Farey sequences of given denominator or order. i.e. The Farey sequence of order N is the sequence with N as the maximum denominator. Let’s look at alternative ways to compute these fractions.

Four Lots of Haskell

To start writing Haskell functions we first create a suitable data type for fractions – very much like the type that allowed for continued fractions but somewhat simpler. A fraction is just the ratio of two integers:

and I’ve added a few utility instances and a function to simplify a fraction. This allows us to create fractions and reduce them. e.g.

A brute force way of calculating a Farey sequence of order N is just to enumerate all the possible combinations, remove duplicates and sort them… like this.

Farey One

running some examples in ghci we get

As can be imagined this function is not particularly efficient. Enabling timing in ghci and we get these quite long calculation times.

There are more efficient ways of calculating these sequences.

Farey Two

One way is to take a sequence of order N (i.e. the largest denominator is N) and repeatedly compare adjacent fractions and, whenever the denominators added together give N + 1, insert between the adjacent fractions a new fraction with denominator (N + 1) and numerator equal to the sum of the adjacent fractions numerators.

The maxDenom is just a right fold, initialised at 1, that takes the largest denominator on each step. The function fareyFromPreviousSeq takes an existing sequence and ‘consumes’ it from the left using fractions from the supplied sequence and inserting new fractions when the insertion condition is met.

This allows us to compose calls to fareyFromPreviousSeq like this.

Or, pleasingly, take what we want from an infinite list of sequences 🙂

which gives all sequences leading to the final one. To get just the final sequence we use last. i.e.

Even generating all prior sequences this method is much quicker than Farey One. e.g.

Yet another way is to start with the initial sequence and repeatedly insert new fractions into it. Here is…

Farey Three

fareyForOrder starts with the initial sequence [F 0 1, F 1 1] and recursively builds up the required sequence from the initial one. The execution times are, as would be expected, an improvement on Farey Two.

The final Farey function is one based on a recurrence relation involving three consecutive Farey fractions.

Farey Four

The proof of the recurrence relation is an exercise in the rather excellent book “Concrete Mathematics” by Ronald L. Graham, Donald E. Knuth and Oren Patashnik or look here on Wikipedia.

As can be seen, it ‘pacmans’ its way along creating the next fraction (F p q) from the previous two, F a b and F c d. Of the four Farey functions this one, as might be expected is faster than the others, calculating Farey 10000 in less than a minute.

No doubt there are other ways of implementing these functions and I’d be please to hear from anyone who wants to add theirs!

Finally here’s a neatly formatted pyramid of Farey fractions up to order 9.

0/1 1/1
0/1 1/2 1/1
0/1 1/3 1/2 2/3 1/1
0/1 1/4 1/3 1/2 2/3 3/4 1/1
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1

The next post will be showing a geometrical interpretation of these fractions.

All the code is in Github and thanks for reading!

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top