©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

 

---

 

Show more

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.

Hide

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

 

Farey F? Stern-Brocot SB? Calkin-Wilf CW? RESET ⇑ ⇓

Ford
Circles F
? View
order View
Path P
? View
Binary B
? Continued
Fraction CF
? Tree
QUIZ

This document requires an HTML5-compliant browser. LEVEL ▶ 0 3 6 ROW ▶ 0 31 32

Stern-Brocot Continued Fraction of order 3: \[[0,3,1,3,1]\] \[0+\cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}\] Convergent ViewMatrix ViewFocus on a convergent?Another SBCF order?Explore Stern-Brocot FurtherLocating Terms in the TreesLinking the Trees

Farey F? Stern-Brocot SB? Calkin-Wilf CW? RESET ⇑ ⇓

App generated by GXWeb

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

---

 

Show

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?

 

---

 

Hide

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

---

 

Hide

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 Stern-Brocot Continued Fraction of order 3 (Left Branch) is

$$[0,3,1,3,1]$$

(The Right Branch Stern-Brocot Continued Fraction of order 3 is $[3,1,3,1]$)

Perhaps simpler still is the expanded Stern-Brocot Continued Fraction of order 3:

$$[0,3,1,3,1,5,1,3,1]$$

This Stern-Brocot Continued Fraction delivers ALL the terms of the Stern-Brocot tree up to the specified level. Note that the more compact form of order n has $1+2^{n-1}$ terms, while the expanded form has $1+2^n$ terms. $$0+\cfrac{1}{3-\cfrac{1}{1-\cfrac{1}{3-\cfrac{1}{1-\cfrac{1}{5-\cfrac{1}{1-\cfrac{1}{3-\cfrac{1}{1}}}}}}}}$$ => $$[\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\frac{3}{2},\frac{2}{1},\frac{3}{1},\frac{1}{0}]$$

---

$$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 Tree 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}$$

 

---

Show

But where do these numbers 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

 

---

 

Hide

Back to Index

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

---

 

Hide

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

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

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

3. 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?

---

Show

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, filling in the remainder of the Calkin-Wilf Tree is a little more challenging! 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^3-2^2+2^1\) => (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.

---

Show

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 (rac{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

---

Show

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!):

1. Take its reciprocal.

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

3. Rewrite this continued fraction backwards, then

4. 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?

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

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

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

4. ⇒ \( [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?

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

2. ⇒ \( [3,1]\)

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

---

Hide

Back to Index

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

 

Show

Explore Further

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Climbing Around Fraction Trees with GXWeb (YouTube 5:31) ⇒

Unpacking the Stern-Brocot Continued Fraction (YouTube 7:34) ⇒

Navigating the Fraction Trees (YouTube 11:25) ⇒

 

---

 

Explore Farey Numbers and Fraction Trees
Further ⇒

Explore Continued Fractions
Further ⇒

Explore Kissing Circles
Further ⇒

GXWeb Jigsaws
and Quizzes ⇒

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

 

Show

Share Your Results

 

Enter your name:	? Abel, Nils Agnesi, Maria Bernoulli, Daniel Cantor, Georg Descartes, Rene Euler, Leonhard Fermat, Pierre Galois, Evariste Germain, Sophie Hypatia Johnson, Katherine Liebniz, Gottfried Lovelace, Ada Monge, Gaspard Newton, Isaac Noether, Emmy Pythagoras Ramanujan, Srinivasa Riemann, Bernhard Sylvester, James Tao, Terence Weierstrass, Karl' Zeno
My class:
Email to:

Session report length: 0 characters.

⇒ Web

⇒Email

Clear

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

---

 

Hide QR

Share with QR Code

GXWeb Fractured Fractions Jigsaw

Send Your Own QR Code

Reset QR Code

Send Web Address ⇑

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

 

---

---

 

Show

Construct your own Model with GXWeb

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

Hide

 

---

---

 

Show

Behind the Scenes

Back to Top

Jump to Model

Mathematical ToolBox

About the Stern-Brocot Continued Fraction

Navigating the Fraction Trees

 

View JavaScript GXWeb Code (gxftree.js)

View JavaScript Shared Code (latex2math.js)

View JavaScript Shared Code (sharedcodend.js)

 

---

 

Learn How: Create your own GXWeb Assessment Task

Learn How 2: Take GXWeb to the Next Level

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

---