Farey Numbers and Linked Lists

Farey Numbers

Farey numbers are fractions. The first two Farey numbers are \(\displaystyle\frac{0}{1}\) and \(\displaystyle\frac{1}{1}\). If you have two Farey numbers \(\displaystyle\frac{a}{c}\) and \(\displaystyle\frac{b}{d}\), you can make a new Farey number \(\displaystyle\frac{e}{f}\) by summing their numerators and denominators.

\[ \displaystyle\frac{e}{f} = \frac{a+b}{c+d} \]

The new Farey number will always be strictly between the first two, so if \(\displaystyle\frac{b}{d}\) were the larger of the two then

\[ \frac{a}{c} < \space\frac{a+b}{c+d}\space< \frac{b}{d} \]

We have two Farey numbers, so we can make another one between them. According to the rule, that number is \(\displaystyle\frac{0 + 1}{1 + 1}=\frac{1}{2}\) . Our list of Farey numbers is now \[ \Biggl \{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \Biggr \} \]

Now we can make two more Farey numbers. Inserting between \(\displaystyle\frac{0}{1}\) and \(\displaystyle\frac{1}{2}\) gives us \(\displaystyle\frac{0+1}{1+2}=\frac{1}{3}\). Inserting between \(\displaystyle\frac{1}{2}\) and \(\displaystyle\frac{1}{1}\) gives us \(\displaystyle\frac{1+1}{2+1}=\frac{2}{3}\). Now our list is

\[ \Biggl \{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \Biggr \} \]

Now we can make four more Farey Numbers. If we make them all, our list becomes

\[ \Biggl \{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \Biggr \} \]

We can continue making new Farey numbers forever and we’ll never make the same Farey number twice. Also we’ll never make Farey numbers that are equivalent fractions. So, for example, since we’ve already made \(\displaystyle\frac{1}{2}\) that means we’ll never make \(\displaystyle\frac{1}{2}\) again, and we’ll also never make any of \(\displaystyle\Biggl\{\frac{2}{4},\frac{3}{6},\frac{4}{8}, ... \Biggr\}\).

Linked Lists

A linked list is sequence of elements, each one linked to the next. The first two elements are the begin and end of the list.

If you have two elements of a linked list, you can make a new element between them. We have the begin and end of the list, so we can make another one between them. Our linked list now looks like this.

We need a name for that node so we can talk about it. It was inserted between begin and end, so we’ll call it be.

Now we can make two new elements. Inserting between b and be gives us bbe. Inserting between be and e gives us bee. Now our list is

Now we can make four new elements. If we make them all, our list becomes

We can continue making new elements forever and we’ll never make an element with the same name.

Squint Real Hard

If we squint real hard, our strings of bs and es map directly to the Farey numbers! The number of es in the string is the numerator of the Farey number, and the length of the string is the denominator of the Farey number.

Why is that interesting?

If you use Farey numbers to name the elements of linked lists as they’re inserted, the structure (and a good bit of the history) of the linked list is completely specified by those names. You can break all the links and reassemble the list by starting at the empty list and following the Farey number generation process. The first element you insert will always be the one called \(\displaystyle\frac{1}{2}\), which will always make the \(\displaystyle\frac{1}{3}\) and \(\displaystyle\frac{2}{3}\) spots available for insert, and so on.

The Farey numbers are a neat coordinate system for linked lists.