A Stern View.

 

 

We all know the Fibonacci sequence and how it is generated…

1, 1, 2, 3, 5, 8,…

We just add the ‘previous’ pair to get the next number and then move along to the next pair.
An interesting variation on this is to add adjacent pairs and write down their sum as before but, after appending the sum, also append the second digit of the pair just added and this gives…

1, 1, 2, 1, 3, 2, 3, 1 …

Starting with 1, 1

1 + 1 -> 2 – append 2 and then copy forward 1
1 + 2 -> 3 – append 3 and then copy forward 2
2 + 1 -> 3 – append 3 and then copy forward 1
etc.
This sequence gets longer and longer whilst the ‘processing’ lags behind! Each step of the production creates two terms and moves along by just one term.

The sequence is the so called Stern-Brocot sequence (A002487) and the sequences can be used, quite easily, to generate all rational numbers in their simplest form (i.e. the numerator and denominator are co-prime).
So, first some Haskell showing three alternative ways of generating the sequence. The first way will be a brutal list manipulation with a final reverse at the end. The second function will use a recurrence relation to calculate the terms. The final one (and my favourite) will recursively stitch together two lists – the second being the tail of the first one.

Stern One

This one is the least elegant and requires an integer indicating how many terms to generate.

Here the key function is update which uses two indices to determine which are the list elements to add together and which one to copy forward. This is the snippet b:a + b:xs that creates each new term.

Sample output:

The next implementation is somewhat neater and uses a recurrence relation defined in (A002487)

Stern Two

The recurrence equations are:

a_0 = 0
a_1  = 1
When\  n > 0\  then\  a(2n) = a(n), \   a(2n+1) = a(n) + a(n+1)
which converts quite easily to

the final implementation is, I think, quite elegant and encapsulates what I truly enjoy about Haskell.

Stern Three

The similarity between stern3 and the canonical Haskell implementation of the Fibonacci sequence,
fibs = 0 : 1 : zipWith (+) fibs (tail fibs) is not entirely coincidental 🙂

We now have several ways of generating 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7… Now, using the sequence, we can generate fractions by taking elements by pairs (a, b) setting the numerator to a, the denominator to b and then moving along by one. i.e
1/1, 1/2, 2/1, 1/3, 3/2… and the interesting thing is that each fraction appears in its lowest form and appears once only and that all (positive) fractions will be in the list. This leads to the next section entitled:

Stern Fractions

Here’s a first pass at generating fractions. (Note that the Fraction type was introduced in the post Count the Fractions )

and we can combine it with one of the stern functions to get

and an alternative fracs function is

and zip <*> tail is quite a useful idiom that sort of enables fmap-ing using pairs of items from a list. For example

λ-> zip <*> tail $ ([1,2,3,4,5,6]::[Int]) gives  [(1,2),(2,3),(3,4),(4,5),(5,6)]

Typically the fractions just generated are viewed in a tree know as the ‘Stern-Brocot Tree‘. Creating such a tree and displaying it will be done in detail in the next post. In the meantime here is an example of such a tree, rendered using tree-view, note that it is shown collapsed initially, just click on the fractions to expand/collapse them.

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