Climbing Around Fraction Trees

©2022 Compass Learning Technologies ← GXWeb Farey Numbers, Fraction Trees and Kissing Circles → Climbing Around Fraction Trees

Climbing Around Fraction Trees

and Unpacking the Stern-Brocot Continued Fraction

Saltire Software, home of Geometry Expressions and GXWeb

Symbolic computations on this page use Nerdamer Symbolic JavaScript to complement the in-built CAS of GXWeb

Explore Bill Gosper (1972): Continued Fraction Arithmetic

Calkin and Wilf (1999): Recounting the Rationals

Bates, B., Bunder, M. and Tognetti, K. (2010): Locating Terms in the Stern–Brocot Tree

Bates, B., Bunder, M. and Tognetti, K. (2010): Linking the Calkin–Wilf and Stern–Brocot trees

Bruce Bates (2014): The Stern-Brocot Continued Fraction

Ben Gobler: Listing the Rationals Using Continued Fractions (YouTube 12:40)

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.

Introduction

GXWeb Fraction Tree Model

Mathematical ToolBox

Breaking Open the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Explore Further

Share your Results

Model with GXWeb

Behind the Scenes

Did You Know that Fractions Grow on Trees?

Or that (Fraction) Trees Can Grow from (Continued) Fractions?

Suppose you wanted to make a list of all the rationals... 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.

Ford Circles offer a beautiful way to help us to better visualise these special numbers. Imagine each term of a Farey Sequence is plotted on a number line. Then draw a circle on each point with a particular radius(!?) which allows it to just touch (to kiss!) any adjacent circle.

There are, of course, other ways to approach the problem of listing (enumerating) the rationals.

A second approach may be found in the form of Fraction Trees - Farey Trees, Stern-Brocot and Calkin-Wilf Trees offer amazing insights into the nature and structure of rational numbers, and their relationship with continued fractions. (Did you know that these fraction trees provide simple ways, not only to list all the rationals, but to express them in continued fraction form?)

In particular, we will discover a special continued fraction which generates all the rational numbers in the Farey Tree, and from these to the Stern-Brocot and Calkin-Wilf Trees!

Can you see how the fractions at each level are calculated from their parents?

How do the paths to each term lead to continued fractions?

How can you tell which level of the Stern-Brocot or Calkin-Wilf trees to look in to find a particular rational number?

Investigate the amazing Stern-Brocot continued fraction. Explore further using the buttons and sliders below - then try the quiz to predict the next level.

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

LEVEL

0 2.5 5

ROW

0 31 32

App generated by GXWeb

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Mathematical ToolBox

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

About the MathBoxes...

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?

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Breaking Open the Stern-Brocot Continued Fraction

Back to Top

Jump to Model

Mathematical ToolBox

Navigating the Fraction Trees

The Stern-Brocot Tree has its own continued fraction! (With thanks to Dr Bruce Bates from the University of Wollongong)

(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]\))

\[0+\cfrac{1}{3-\cfrac{1}{1-\cfrac{1}{3-\cfrac{1}{1}}}}\]
Each convergent of the Stern-Brocot continued fraction gives a term in the Farey Sequence of order 3:
\[\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{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:
\[\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}\]
Can you see how this may be expressed as a product of matrices?
\[\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 3 & -1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 3 & -1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 1 & 0 \\ \end{bmatrix}\] \[= \frac{1}{1}\] ⇒ \[\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 3 & -1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 3 & -1 \\ \end{bmatrix} => \frac{0}{-1}, \frac{1}{3}\] \[\begin{bmatrix} 1 & 0 \\ 3 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ 2 & -3 \\ \end{bmatrix} => \frac{1}{2}\] \[\begin{bmatrix} 1 & -1 \\ 2 & -3 \\ \end{bmatrix} \begin{bmatrix} 3 & -1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 3 & -2 \\ \end{bmatrix} => \frac{2}{3}\] \[\begin{bmatrix} 2 & -1 \\ 3 & -2 \\ \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & -3 \\ \end{bmatrix} => \frac{1}{1}\]

So where does this mysterious continued fraction come from?

Drag the large point on the left (⇵) to switch between tree and sequence views.

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Navigating the Fraction Trees

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

References:

Bates, B., Bunder, M. and Tognetti, K. (2010): Locating Terms in the Stern–Brocot Tree

Bates, B., Bunder, M. and Tognetti, K. (2010): Linking the Calkin–Wilf and Stern–Brocot trees

Suppose I wish to know which fraction occurs in the 17th position of the Farey, Stern-Brocot or Calkin-Wilf trees.

Or I would like to know where exactly to find \(\frac{5}{8}\) in the Stern-Brocot or Calkin-Wilf trees.

Finally, if I know the j-th vertex in level k in the Stern-Brocot tree, how can I find the corresponding vertex in the Calkin-Wilf tree? And vice-versa?

Challenge 1

One approach to the first question involves expressing the path to each node in binary form, and converting this to a continued fraction. This has been dealt with in detail elsewhere: Follow a Binary Path to Continued Fractions.

A key focus of our current exploration is the Stern-Brocot Continued Fraction, which offers a lovely way to identify the position of any term: convert the fraction to continued fraction form and add the terms to find the Stern-Brocot or Calkin-Wilf order. Then use the convergent corresponding to your value to locate its position in the Stern-Brocot tree.

The Stern-Brocot Continued Fraction gives each of the terms of the Farey Tree, which serve as the left branch of the Stern-Brocot AND the even-numbered terms of Calkin-Wilf. While they can readily also give the Stern-Brocot right branch through reciprocal mirroring, they are less effective in filling in the remainder of the Calkin-Wilf Tree.

Both these methods assume an ordering of the Farey and Stern-Brocot trees from right to left, counting from the top, as shown - AND an odd-numbered continued fraction!

Quite a different approach to navigating the trees comes with the use of normalised additive factorisation instead of the binary representation used above.

Any integer can be represented using an (odd-numbered) series of powers of 2, with alternating sums and differences. For example, the normalised additive factored form of 6 is [3,2,1] => 6 = \(2³-2²+2¹\) => (6 = 8-4+2)

Normalised additive factors can be used to find the value and position of any term in both Stern-Brocot and the Calkin-Wilf trees. These use a left-to-right ordering system for the vertices of the trees AND an odd-numbered continued fraction.

To build the continued fraction for term 3 (=> {2,1,0}) of level 3 of the Calkin-Wilf tree, for example, begin with the last term of the normalised additive factor list: [0].

From right to left, find the difference between each of the additive factors, and finally the difference between the term number (3) and the first term of the additive factors list (2) => 3 - 2 = 1

The continued fraction for term 3 of level 3 of the Calkin-Wilf tree is \([0,1,1,1] = \frac{2}{3}\). This is also term 6 of the full tree, since there are 3 terms preceding level 3.

Challenge 2

For Stern-Brocot, the process is similar but reversed (with an odd number of terms for Stern-Brocot and an even number of terms for Calkin-Wilf). First, though, we distinguish between fractions less than 1 as opposed to those greater than or equal to 1.

For Stern-Brocot:

Step 1. If the number is less than 1, discard the leading 0 and next term. (If greater than 1, just start with all the terms of the continued fraction.)

Step 2. Add remaining terms and subtract 1 for the first element of your NAF.

Step 3. Remove the current leading term and return to step 2.

Example 2.1: \(\frac{3}{5}\) => [0,1,1,1,1] lies in level 4 of the Stern-Brocot and Calkin-Wilf trees (since the sum of the terms add up to 4!)

This number is less than zero, so discard the first two terms, leaving just <1,1,1>. Add these and subtract 1 to get 2, the first term of our normalised additive factor.

Discard the first term to get <1,1>. Add and subtract 1 => 1. Our NAF is now {2,1}.

One more round to get 1-1 = 0, and our normalised additive factors for \(\frac{3}{5}\) => {2, 1, 0} = \(2^2 - 2^1 + 2^0 = 4 - 2 +1 = 3\).

Hence \(\frac{3}{5}\) is term 3 of level 4 of the Stern-Brocot Tree.

Example 2.2: \(\frac{10}{7}\) => [1, 2, 3] lies in level 6 of the Stern-Brocot and Calkin-Wilf trees (since the sum of the terms add up to 6!)

This number is greater than zero, so add all terms <1 + 2 + 3>. Add these and subtract 1 to get 5, the first term of our normalised additive factor.

Discard the first term to get <2 + 3>. Add and subtract 1 => 4. Our NAF is now {5, 4}.

Once more to get 3 - 1 = 2, and our normalised additive factors for \(\frac{10}{7}\) => {5, 4, 2}.

The normalised additive factor form of \(\frac{10}{7}\) = [1,2,3] is {5,4,2} => \(2^5-2^4+2^2\)= 32 - 16 + 4.

\(\frac{10}{7}\) is term 20 of Stern-Brocot level 6

Challenge 3

Finally, we deal with our third question: how do I map vertices between Stern-brocot and Calkin-Wilf trees? The answer is surprisingly simple!

To convert the jth entry in the kth level of the Stern–Brocot tree into the jth vertex in the kth level of the Calkin–Wilf tree (and back the other way!):

Take its reciprocal.

Express this reciprocal as a continued fraction possessing an even number of terms. (This will be either the long or short form), then

Rewrite this continued fraction backwards, then

Subtract 1 from the first term and add 1 to the last term.

And this method works in both directions!

Example 3.1: The 7th entry in the 4th level of the Stern–Brocot tree is \(\frac{5}{2} = [2,2]\). What is the 7th vertex in the 4th level of the Calkin–Wilf tree?

\(\frac{2}{5} = [0,2,2]\)

⇒ \( [0,2,1,1]\)

⇒ \( [1,2,1,0]\)

⇒ \( [0,1,2,1] = \frac{3}{4}\)

Example 3.2: The 7th entry in the 4th level of the Calkin-Wilf tree is \(\frac{3}{4} = [0,1,2,1]\). What is the 7th vertex in the 4th level of the Stern–Brocot tree?

\(\frac{4}{3} = [1,3]\)

⇒ \( [3,1]\)

⇒ \( [2,2] = \frac{5}{2}\)

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Explore Further

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Share Your Results

Enter your name:

My class:

Email to:

Session report length: 0 characters.

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Share with QR Code

GXWeb Fractured Fractions Jigsaw

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 Fractured Fractions Jigsaw, 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!

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Construct your own Model with GXWeb

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Behind the Scenes

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

©2022 Compass Learning Technologies ← GXWeb Farey Numbers, Fraction Trees and Kissing Circles ← Climbing Around Fraction Trees