It’s just fun playing around with Stern-Brocot trees and a bit of Haskell…! For any fraction on the Stern-Brocot tree there is just one path to it from the root. That path can written as a sequence of left or right ‘turns’ at each node depending on whether the target node is smaller or larger than the current node. This leads to the Stern Path For example in this small tree the path to, say, 4/5 is, from 1/1, LRRR. The fraction 5/2 has path RRL. To get to 5/8 we go LRLR… and so on. (If you want to Read More
Tag: haskell
A Stern Tree
The purpose of this post is to show how to generate a visual representation of the Stern-Brocot tree, like this: SBTree the rendering of which uses Northwood’s GoJS Javascript library. To create to a rendered Stern-Brocot tree we need to: Create a binary tree datatype with supporting functions. Generate a specific type of binary tree – i.e. a Stern-Brocot tree. Examine the GoJS model details and write some Haskell to map the binary tree to the Javascript. Binary Trees Yes, I could have found an existing Haskell library for binary trees – but really, where’s the fun in that? A Read More
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 Read More
Ford gets Complex!
Not too complicated and just a different view of Ford’s circles and a way of morphing them along with a bit of animation. It’s a continuation of the previous post and there are two parts to it – the real bit and the imaginary part. The Real Part To start with we take fractions not between 0 and 1 but rather between -n and n. A rough and ready way is
|
1 2 3 |
-- fractionsN :: Integer -> [Fraction] fractionsN n = nub [ reduce (F p q) | p <- [-n..n], q <- [-n..n]] |
where we take all possible pairs and reduce them. Note we allow 0 as a denominator so as to be consistent with the Farey sequence. For Read More
Ford and his Circles.
A Ford circle is a circle derived from a pair of numbers that are co-prime, i.e. they have no common factors. For a pair of co-prime integers p and q the Ford circle has radius r and centre at a point P(x, y) where r = 1/(2q^2) and P = (p/q, r) No matter what co-prime numbers, p and q, are used to create Ford circles the circles never intersect and they are all tangential to the horizontal axis. Now, we could generate ‘random’ Ford circles by picking any old co-prime pair (p, q). However, the Farey Read More
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 For Read More
Squares and Graphs
Recently I came across this intriguing little puzzle… Take the integers 1..n and, if possible, arrange them in a list in such a way that consecutive numbers in the list add up to a square number. Use each number 1..n once only. In exploring this puzzle I started writing down the numbers and forming a graph where two numbers are connected if they add up to a square. Drawing such graphs is fun but slightly tedious for, for example, [1..300]… Here’s such a graph for numbers 1..15. Starting at 8 then 1 etc. and following the path gives the solution Read More
Continued Fractions, Pell’s Equation and Scary Numbers.
This is Pell’s equation: where n is a positive integer that isn’t a perfect square. Only integer solutions for x and y are sought and if n is not a perfect square then there are infinitely many integer solutions. It can be shown that the convergents of the continued fraction (CF) for the square root of n contains a solution known as the Fundamental Solution (FS). In practice this fundamental solution is the first convergent that satisfies the equation under consideration. Once this solution is known then all other solutions can be calculated from a simple recurrence relationship. i.e. If Read More
More Continued Fractions Continued.
In the post Parsers to Fractions to Square Roots! we looked at continued fractions (CFs) expressed in list format and used that format to calculate the square root of integers. The technique didn’t really explore an effective way of generating the list form for a CF. In this short post we’ll look at how to calculate the CF list format for the square root of an integer. Then, from the list, calculate the convergents, each of which gives a better and better value for the square root. (The details of convergents have been covered in Continued Fractions Continued.) With a Read More
The expressiveness of Haskell – Split a List.
Just recently playing around with one of the excellent Advent of Code problems (specifically 2015 question 6 ) a possible solution involved splitting a list into two parts where the first element goes into the first part, the second element into the second part and so on. For example [1, 2, 3, 4, 5, 6] -> [1, 3, 5], [2, 4, 6] So, in terms of function signatures we can write splitList :: [a] -> ([a], [a]) Notice there’s no constraint on the type in the list, it’s a very general function. One way of doing this is is to make use of pattern matching Read More