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.
|
1 2 3 4 5 6 7 8 9 |
-- stern1 :: Integer -> [Integer] stern1 n = reverse ns where (_, _, ns) = head . dropWhile f . iterate update $ (0, 1, [1,1]) f (_, _, xs) = (toInteger . length $ xs) <= n update (ia, ib, xs) = (ia + 1, ib + 1, b:a + b:xs) where len = length xs - 1 a = xs !! (len - ia) b = xs !! (len - ib) |
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:
|
1 2 3 |
-- λ-> stern1 25 [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5] |
The next implementation is somewhat neater and uses a recurrence relation defined in (A002487)
Stern Two
The recurrence equations are:
|
1 2 3 4 5 6 7 8 9 |
-- stern2 :: [Integer] stern2 = [next n | n <- [1..]] where next :: Integer -> Integer next n | n < 2 = n | even n = next (n `div` 2) | otherwise = next n' + next (n' + 1) where n' = (n - 1) `div` 2 |
the final implementation is, I think, quite elegant and encapsulates what I truly enjoy about Haskell.
Stern Three
|
1 2 3 4 5 |
-- stern3 :: [Integer] stern3 = 1 : 1 : knit (tail stern3) stern3 where knit (a:as) (b:bs) = a + b : a : knit as bs |
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 )
|
1 2 3 4 5 |
-- fracs1 :: [Integer] -> [Fraction] fracs1 [] = [] fracs1 [p,q] = [F p q] fracs1 (p:q:ns) = F p q : fracs1 (q:ns) |
and we can combine it with one of the stern functions to get
|
1 2 3 |
-- λ-> take 30 . fracs1 $ stern3 [1/1,1/2,2/1,1/3,3/2,2/3,3/1,1/4,4/3,3/5,5/2,2/5,5/3,3/4,4/1,1/5,5/4,4/7,7/3,3/8,8/5,5/7,7/2,2/7,7/5,5/8,8/3,3/7,7/4,4/5] |
and an alternative fracs function is
|
1 2 3 |
-- fracs2 :: [Integer] -> [Fraction] fracs2 xs = fromTuple <$> (zip <*> tail $ xs) where fromTuple (p, q) = F p q |
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!