With thanks to Dr Keith Tognetti for pointing me in the direction of continued fractions many years ago and igniting in me a life-long passion, and to Dr Bruce Bates (both of the University of Wollongong) for revealing to us all the beautiful Stern-Brocot Continued Fraction. With colleague Dr Martin Bunder they have brought to light many wonderful and often surprising connections between binary trees and continued fractions.
Welcome to the Fractured Fractions Collection!
Try the Continued Fraction JigSaw! Just rearrange the squares to fill the given rectangle, and then press INPUT (or the JIGSAW button again) to enter your answer.
Then go on and explore some of the wonderful connections between continued fractions and some surprising and important corners of mathematics. Did you know, for example, that fractions grow on trees?
Hint: When entering mathematical expressions in the math boxes below (f(x), g(x) and h(x)), use the space key to step out of fractions, powers, etc. On Android, begin entry by pressing Enter.
Type simple mathematical expressions and equations as you would normally enter these: for example, "x^2[space]-4x+3", and "2/3[space]". For more interesting elements, use Latex notation (prefix commands such as "sqrt" and "nthroot3" with a backslash (\)): for example: "\sqrt(2)[space][space]". Learn More?
Interested to learn more? Delve more deeply into Continued Fractions with GXWeb Fractured Fractions and then on to the following...
Golden Numbers and More
Try \(\frac{34}{21}\), \(\frac{55}{34}\) and \(\frac{89}{55}\). Notice anything? What comes next?
This might just begin a search for the most beautiful (and most irrational) of numbers...! And make sure you take a moment to explore the archimidean spiral along the way:
Perhaps take another moment or two to also explore the metallic means: \[x=a + \cfrac{1}{x} => x^2=a\cdot x+1 => \frac{(a+\sqrt(4+a^2)}{2}\] and the noble numbers:\[x=a + \cfrac{1}{1-a+x} => (2\cdot (x-a)+1)^2 = 5 => \frac{(\sqrt(5)+2a-1)}{2}\].
Fractured Functions: Generalised Continued Fractions
Most of the continued fractions you will come across are likely to be of the simple variety, but the many generalised forms offer so many interesting patterns and possibilities for further exploration! Try a few and see what you discover...
While continued fractions may formally trace their origins to the time of Euclid, continued (binary) logarithms owe their inception to Bill Gosper in his 1972 unpublished paper on continued fraction arithmetic.
In the newly dawning age of personal computers, Gosper recognised both the limitations of continued fractions in dealing with very large and very small numbers, and the possibilities for a new type of binary representation, reducing such numbers to highly accurate arrays of zeros and ones. Gosper described it as a "sort of recursive version of scientific notation"(1972).
This exploration introduces just a taste of the wonderful research of the past decade, exploring these unusual mathematical creatures. The particular focus here is on the multiple continued fraction-like representations for real numbers made explicit through continued logarithms.
While we count ourselves lucky to know of one or two generalized continued fraction forms for most reals, this exploration reveals the relatively simple processes which deliver five distinct forms for most numbers!
Simple Continued Fractions may be defined as follows:
Count the number of times we encounter \[x → x − 1\] before we either reciprocate or terminate. These counts are the terms \[[a_0, a_1,...]\] of our continued fraction.
Continued Logarithms (base \(b\)) (Gosper, 1978) are defined in a similar way by
For \(x \geq b\), divide by \(b\) until the result lies between 1 and \(b\). Count the number of divisions. Continue until you reach 1.
For \(1 < x < b\), subtract 1 from base \(b\) then divide by \((x-1)\). Repeat until the result is equal to 1 (and terminate) or greater than or equal to \(b\) (and start dividing by \(b\) again)..
The continued logarithm for \(19\)\[ => [1,1,1,1,0,1,1,0,1,0,1]_{cl(2)}\]\[ => [4,2,1,1]_{cl(2)}\]
Suppose you wanted to make a list of all the rational numbers between 0 and 1.
How might you start?
One approach might be to begin with the denominators of the fractions: first, list those with denominator 1 - zero and 1: \(\frac{0}{1}, \frac{1}{1} \).
Next, add those with denominator 2: \(\frac{0}{1}, \frac{1}{2}, \frac{1}{1} \).
Add those with denominator 3 ( \(\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \)) and you are on your way to the Farey Sequence! This last would be referred to as the Farey Sequence of Order 3.
There are some wonderful connections between continued fractions and Farey numbers - rational terms of Farey Sequences.
For example, \(\frac{2}{5}\) and \(\frac{5}{12}\) are neighbours in Farey(12), as are \( \frac{6}{19}\) and \(\frac{7}{22}\) in Farey(25). Check their continued fraction forms and try more of your own...
In addition to the Farey Sequence, there are other beautiful ways to display the rationals between 0 and 1, including one which is even more closely related to continued fractions.
The Farey Tree (a subset of the Stern-Brocot Tree) begins with the endpoints of 0 and 1 and uses the mediant to find a fraction between each. As with the Farey sequence, this simply involves forming a fraction by adding the two numerators and the two denominators.
So \(\frac{0}{1}\) and \(\frac{1}{1}\) give \(\frac{0+1}{1+1} = \frac{1}{2}\)
Then \(\frac{0}{1}\) and \(\frac{1}{2}\) give \(\frac{0+1}{1+2} = \frac{1}{3}\) and \(\frac{1}{1}\) and \(\frac{1}{2}\) give \(\frac{1+1}{1+2} = \frac{2}{3}\)
Each subsequent row of fractions is built by continuing this process, stepping either to the left (L) or right (R), beginning from 1. Each \(n\)-th row begins with \(\frac{1}{n}\) and ends with \(\frac{n-1}{n}\).
From \(\frac{1}{1}\), to get to \(\frac{1}{2}\), move down to the Left (L). To form the continued fraction(s), simply add another L or R (it does not matter which because both deliver correct but slightly different results). So for \(\frac{1}{2}\), we could have LL or LR. Begin your continued fraction with zero (since all our fractions - for now! - lie between 0 and 1) and then count each repeated element. Then LL will give the continued fraction \([0, 2]=0+\cfrac{1}{2}\) and LR gives \([0, 1, 1] = 0 + \cfrac{1}{1+\cfrac{1}{1}}\).
In the same way, to get to \(\frac{1}{3}\) from \(\frac{1}{1}\), step LL. Add another L to get LLL (\([0,3]\)) or LLR (\([0,2,1]\)). For \(\frac{2}{3}\) from \(\frac{1}{1}\), step LR. Add another L to get LRL (\([0,1,1,1]\)) or LRR (\([0,1,2]\)).
Any continued fraction ending in 1 can be compacted by adding that trailing one to the previous term.
Finally, note that every element of our Farey Tree can be allocated its own unique number, starting with \(\frac{1}{2}\) as number 1, then stepping down and counting from right to left. This gives \(\frac{2}{3}\) as number 2, \(\frac{1}{3}\) in position 3 and \(\frac{3}{4}\) as the fourth Farey Tree fraction.
Now, suppose instead of L and R we used 1 to represent a step down and to the left and 0 to step down and to the right?
We saw above that the path to fraction number 1 (\(\frac{1}{2}\)) from the starting point of \(\frac{1}{1}\) is simply L to which we add another L to give LL (2) or R for LR (1,1). Now add a 0 at the front to form the equivalent continued fractions [0,2] and [0,1,1].
But instead of L to represent the path, we could use 1. Then add a trailing 1 (11 → 2), and a leading 0 and we have the continued fraction [0,2] (since we are counting repeated elements). If we had added a trailing zero, then after the leading 0 we have one "1" (or L) and one "0" (or R) and so we get [0,1,1], as required.
Now consider a different approach. Suppose I wish to know which fraction occurs in the 17th position of our tree.
In binary form, 17 = 10001 (1x16, 0x8, 0x4, 0x2, 1x1). This can also be expressed as the path LRRRL.
Adding a leading zero, and a trailing L leads to the continued fraction [0,1,3,2] (or [0,1,3,1,1] if we had added a trailing R). These both represent the fraction \(\frac{7}{9}\) which is indeed our 17th fraction!
Wait... what?
So I can find the continued fraction of any rational between 0 and 1 by expressing its position on the Farey Tree as a binary number, add a 0 or 1 at the end, count the repeated elements and stick a 0 at the front?
In fact, there is one final bonus. What if we don't add the zero at the front? Then instead of \(\frac{7}{9}\) we get \(\frac{9}{7}\) and suddenly we are no longer restricted to rationals between 0 and 1 but potentially any rational number could be expressed in this way!
We are now in the realm of the Stern-Brocot Tree, of which our Farey Tree is just one half!
Take some time to explore this amazing tree, then try the questions which follow.
This expanded version of the Stern-Brocot Tree covers all rational numbers using symmetry and reciprocals!
You will find the Farey Tree as the left half of the mirror image making up this tree - rational numbers between 0 and 1 to the left; all other rationals on the right.
(Note that this is not the usual simple continued fraction with all numerators equal to 1. This is a general continued fraction - all but the leading numerator equal -1. For convenience, we will use the continued fraction list form below, but a stricter form might be [(0,1),(3,-1),(1,-1),(3,-1),(1,-1)].)
The (Left Branch) Stern-Brocot Continued Fraction of order 3 is
\[[0,3,1,3,1]\]
(The Right Branch Stern-Brocot Continued Fraction of order 3 is \([3,1,3,1]\))
Adding the terms from the right-branch Stern-Brocot continued fraction (above) OR just some reciprocal mirroring of the terms, we then get the full Stern-Brocot sequence of order 3:
So where does this mysterious continued fraction come from?
Order
(0)
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15...
2
(0)
2
1
3
(0)
3
1
3
1
4
(0)
4
1
3
1
5
1
3
1
5
(0)
5
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
Can you see a pattern?
Not an easy one at all...
Hint: The tree(s) we are building are binary. Each row increases by a multiple of two as each term on one row is the parent of two children.
Look again at our continued fraction arrays. The first two terms are easy: the leading zero of a continued fraction ensures that the value lies between 0 and 1. The second term is the order number.
Now study the remaining terms in the n-th sequence: all odd-numbered terms are given the value 1.
So what about the even numbers? 2 → 3 (\(2\cdot 1+1\))? 4 → 5 (\(2\cdot 2+1\))? But for 6, \(2\cdot 3+1\) does not equal 5, and for 8, \(2\cdot 4+1\) does not equal 7 as required.
The secret here lies in counting the number of 2s in the prime factorisation of each number!
Let b be the number of times 2 occurs as a factor of each number:
\(2=2\cdot 1\) so b = 1 and \(2\cdot b + 1 = 3\).
\(4=2\cdot 2\cdot 1\) so b = 2 and \(2\cdot b + 1 = 5\).
\(6=2\cdot 3\) so b = 1 and \(2\cdot b +1 = 3\).
\(8=2\cdot 2\cdot 2\cdot 1\) so b = 3 and \(2\cdot b +1 = 7\).
Order
(0)
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15...
n → b
(0)
n ↓ b
20 ↓ 0
21 ↓ 1
20\(\cdot\)3 ↓ 0
22 ↓ 2
20\(\cdot\)5 ↓ 0
21\(\cdot\)3 ↓ 1
20\(\cdot\)7 ↓ 0
23 ↓ 3
20\(\cdot\)9 ↓ 0
21\(\cdot\)5 ↓ 1
20\(\cdot\)11 ↓ 0
22\(\cdot\)3 ↓ 1
20\(\cdot\)13 ↓ 0
21\(\cdot\)7 ↓ 1
20\(\cdot\)15 ↓ 0
\(2\cdot b+1\)
(0)
n
1
3
1
5
1
3
1
7
1
3
1
5
1
3
1
As we see above, the Stern-Brocot Tree adds a symmetrical but reciprocal copy of the Farey Tree.
Where the terms of the Farey Tree all lie between 0 and 1, their reciprocals, of course, are all greater than 1.
In this way, the Stern-Brocot Tree offers a listing of ALL rationals.
Explore the Calkin-Wilf Tree
The Calkin-Wilf tree(or Tree of All Fractions) is another binary tree which is obtained by starting with the fraction 1/1 and (this time!) adding \(\frac{a}{a+b}\) and \(\frac{a+b}{b}\) iteratively below each fraction \(\frac{a}{b}\).
The Calkin-Wilf Tree was only developed in the year 2000 by Neil Calkin and Herb Wilf (demonstrating that there is still much beautiful and useful mathematics to be discovered), and is also similar to the binary tree of Johannes Kepler (1619) (The image ⇒ shows the Calkin-Wilf rule on the left and Kepler's on the right).
This tree (like the Stern-Brocot tree) generates every rational number. Writing out the terms in a sequence gives
The sequence has the property that each denominator is the next numerator. That means that the nth rational number in the list looks like \(\frac{b(n)}{b(n + 1)}\) (n = 0, 1, 2, . . .), where
Studying this continued fraction (\(\frac{e^2+1}{e^2-1} = [1, 3, 5, 7, 9, 11...]\)) got me thinking about a continued fraction which should be even simpler: \([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\). Surely this should be given by a common and recognisable real number? Well, how wrong I was! Welcome to the world of Bessel functions!
The factorial function is well known - \(3! = 3 \cdot 2 \cdot 1 = 6,\) \(4! = 4 \cdot 3 \cdot 2 \cdot 1 = 12,\) \(n! = n \cdot (n-1) \cdot (n-2)...\)
But what happens in between? The Gamma function, represented by the Greek capital, \(\Gamma(x)=(x-1)!\) includes all values, not just the integers, and has some interesting properties - especially when you consider the half values of \(\frac{\Gamma(x)}{\sqrt(\pi)}\).
Consider a population, say of fish in a pond. If the pond is fixed in size and limited in the amount of food which it can provide, then the population of fish cannot grow unbounded. In fact, the size of the population itself will limit the growth - as the number of fish (\(x\)) gets large, it will act to slow down the rate of population growth (\(r\)). A simple model of this situation over time is given by the relationship \[f(x)=r\cdot x\cdot (1-x)\]
Suppose you had a list of numbers, for example, myList = [0, 2, 4, 5, 7, 9, 11, 12]. How might you turn each of those list elements into a musical tone - perhaps have 0 represent middle C, and each unit a semi-tone higher. 1 would be C#4, 2 D, and so on. Then myList should give the scale from middle C (C4) to the next C (C5).
Perhaps even write and play your own continued fraction music? You might try dividing a piece into parts and playing in turn with others!
QR Codes are a great way to share data and information with others, even when no Internet connection is available. Most modern devices either come equipped with QR readers in-built, or freely available.
The default link here is the GXWeb Jigsaws and Quizzes, but you can use it as an alternative to sending your assessment data via email, web or share with others in your class. You can even use it to send your own messages!
