©2023 Compass Learning Technologies ← GXWeb Climbing Around Fraction Trees → GXWeb Fraction Tree Playground

GXWeb Fraction Tree Playground

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

GXWeb Fraction Trees Playground: Quick Start (YouTube 3:21)

---

 

Introduction Be Curious... Explore ⇓ Locating Terms in the Trees Paths and Binary Numbers From Path to Fraction Some Matrix Fraction Magic Irrationals in the Fraction Trees Test Yourself ⇓ From Number to Continued Fraction From Continued Fraction to Number From Tree Number to Fraction From Fraction to Tree Number From Fraction to the Complete Stern-Brocot Tree Matrix Multiplication Mathematical ToolKit GXWeb Fraction Trees Model Build Your Own GXWeb Model Share Your Results Explore Further - Dig Deeper Behind the Scenes

 

---

---

Show

Introduction

Index

Jump to MathBox

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!

Farey Tree Order 5 More about farey(5)?

The Farey Sequence of Order 4 follows, \[\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \] while \[\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \] makes up the Farey Sequence of Order 5

 

---

Now imagine arranging these fractions in the form of a tree - a tree which could display every possible fraction, in simplest form - without repetition.

 

---

Fraction Trees (Farey, Stern-Brocot and Calkin-Wilf Trees) offer interesting and useful ways to think about and to visualize rational numbers. The tools provided here offer means to explore and discover some of the surprising connections made possible by these trees - from binary numbers to continued fractions, approximations and even kissing circles! To get started, enter trees(19) in any of the MathBoxes below. You will be presented with the full Fraction Trees Explorer (up to Level 10 - 1023 terms!). This goes well beyond the GXWeb Fraction Trees model which, while offering a great place to start playing, is limited to levels 1 to 3 (up to term 10) of the Farey and Stern-Brocot trees (and 1-4 of Calkin-Wilf, term 15). From the Fraction Trees Explorer, you will readily find that: the 19th term of the Farey Tree (also the left branch of the full Stern-Brocot Tree) is \(\frac{7}{10}\) (all Farey numbers lie between 0 and 1), the 19th term of the right branch of the Stern-Brocot Tree is \(\frac{10}{7}\), and the corresponding term of the Calkin-Wilf Tree is \(\frac{7}{3}\).     And then the fun starts!

Hide

Index

Jump to MathBox

 

---

---

Show

Be Curious...Explore

Index

Jump to MathBox

 

Show

Locating Terms in the Trees

We can see where \(\frac{7}{10}\) and \(\frac{10}{7}\) may be found in the Farey/Stern-Brocot Trees. But where do they occur in Calkin-Wilf? And what about the complete Stern-Brocot Tree - how might we find the location of terms in this tree? And what are normalised additive factors?

Go back to the MathBox and try something bigger than 19: perhaps trees(50)? Or view the trees by level: trees(0,6)? Do you notice any patterns? Note that \(\frac{10}{7}\) is term 19 (15 + 4) of the Right Branch of the Stern-Brocot Tree, where the complete tree includes the Farey Tree as the left branch. In this context, \(\frac{10}{7}\) may be found in the 6th level of the complete tree, and is the 20th term of this level - 15 + 1 Farey terms (including \(\frac{1}{1}\)), and the 4th term on the right. With 5 levels of both Farey and SB Right branches (\(2^5 - 1 = 15 + 15 + 1 = 31\) terms together including \(\frac{1}{1}\)), then \(\frac{10}{7}\) is term 31 + 20 = 51 of the complete Stern-Brocot Tree. Try cf2tree() in the MathBox.

Hard to see the number you want among all those fractions?

Simply tap on any fraction in any tree to view a summary of its properties. For a more complete view, tap the Order View button from the menu bar at top or bottom, or the ⇒ Order button above any of the trees to see the term numbers for each fraction. Zoom in? Tap Trace Path above the trees and enter the fraction you are interested in.

Hide

 

Index

Jump to MathBox

 

---

 

Show

Paths and Binary Numbers

So every rational number has its own unique position in both the Stern-Brocot and Calkin-Wilf Trees - AND its own unique path of left (L) and right (R) steps from the top down to reach this position. Can I use one to find the other?

These are binary trees: each term in Stern-Brocot (and Farey) is the result of the mediant of two "parents", while each Calkin-Wilf term generates two "children". Tap on the Binary View button from the menu bar at top and bottom, or the ⇒ Binary button above the Calkin-Wilf Tree to see the binary form for each term. Then study the Path View of each - can you see how these two are related? Each term number in a tree can be expressed in binary form. For example, 19 = 10011 (base 2). (Enter \(19_{>2}\) in the MathBox) The path to the 19th term in the Farey Tree is LRRLL, the Stern-Brocot path and the Calkin-Wilf path to term 19 are both RLLRR. (Just enter a path - in capitals - in the MathBox)

Hide

 

Index

Jump to MathBox

 

---

 

Show

From Path to Fraction

I have my term number, and from that the binary form, which gives me the unique path for each tree. How do I go from path to continued fraction? And going back the other way - from continued fraction to path, to binary and then to term?

As with most things in life, the answer is "it depends". Consider the examples of Farey(19) ⇒ 10011 ⇒ LRRLL and Stern-Brocot(19) ⇒ 10011 ⇒ RLLRR. For both Farey Tree and Stern-Brocot Right Branch, the path is always one step short for the continued fraction, so add another R or L to the end (why does it not matter?)- giving me either LRRLLL or LRRLLR (Farey) or RLLRRR or RLLRRL (Stern-Brocot Right Branch). Now just count the repeats, from left to right: Right Branch Stern-Brocot(19): RLLRRR ⇒ [1,2,3] or RLLRRL ⇒ [1,2,2,1]. For the Farey Tree, my fraction will always lie between 0 and 1, hence I need to add a 0 as the first term: Farey(19): LRRLLL ⇒ [0,1,2,3] or LRRLLR ⇒ [0,1,2,2,1]. For Calkin-Wilf, we simply read the path in reverse! Calkin-Wilf(19): 10011 ⇒ RLLRR. Calkin-Wilf(19): [2,2,1] (or [2,3]).

Hide

 

Index

Jump to MathBox

 

---

 

Show

Some Matrix Fraction Magic

And what about these matrix forms? Where do they come from?

Continued fractions are commonly represented as the product of 2 x 2 matrices (with the special property of having determinant -1). For example, \[\frac{10}{7} = [1,2,3] \]\[= \begin{bmatrix} 1 && 1 \\ 1 && 0 \end{bmatrix} \cdot \begin{bmatrix} 2 && 1 \\ 1 && 0 \end{bmatrix} \cdot \begin{bmatrix} 3 && 1 \\ 1 && 0 \end{bmatrix} \]\[= \begin{bmatrix} 10 && 3 \\ 7 && 2 \end{bmatrix} \] Alternative approaches exists, however, including one defining two matrices to represent the left and right steps in the path of a rational number: \[L = \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \]\[\ and \ R = \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix}\] Consider the resultant matrix \[ \begin{bmatrix} a && b \\ c && d \end{bmatrix}\] For Farey and Stern-Brocot Trees, the equivalent fraction is given by the mediant: \[ \begin{bmatrix} a && b \\ c && d \end{bmatrix} ⇒ \frac{a+b}{c+d}\] So \[RLLRR_{sb} \]\[= \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \]\[RL^2R^2 \]\[ \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 2 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 2 \\ 0 && 1 \end{bmatrix} \]\[ \begin{bmatrix} 3 && 7 \\ 2 && 5 \end{bmatrix} ⇒ \frac{3+7}{2+5} ⇒ \frac{10}{7}\] For Calkin-Wilf, the product of the path is given simply by \[ \begin{bmatrix} a && b \\ c && d \end{bmatrix} ⇒ \frac{b}{a}\] \[RLLRR_{cw} \]\[= \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \]\[RL^2R^2 \]\[ \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 2 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 2 \\ 0 && 1 \end{bmatrix} \]\[ \begin{bmatrix} 3 && 7 \\ 2 && 5 \end{bmatrix} ⇒ \frac{7}{3}\] Ferreira and Mendes (2016) An alternative Calkin-Wilf approach by Gobler (2022) involves reversing the order of matrix multiplication (multiplying from right to left), resulting in \[ \begin{bmatrix} a && b \\ c && d \end{bmatrix} ⇒ \frac{b}{d}\] \[RLLRR_{cw} ⇒ RRLLR \]\[= \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 1 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \]\[RL^2R^2_{cw} ⇒ R^2L^2R \]\[ \begin{bmatrix} 1 && 2 \\ 0 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 0 \\ 2 && 1 \end{bmatrix} \cdot \begin{bmatrix} 1 && 1 \\ 0 && 1 \end{bmatrix} \]\[ \begin{bmatrix} 5 && 7 \\ 2 && 3 \end{bmatrix} ⇒ \frac{7}{3}\] Both methods appear to achieve the same results.

Hide

 

Index

Jump to MathBox

 

---

 

Show

Irrationals in the Fraction Trees

While our fraction trees represent only rational numbers, they prove highly useful in approximating irrationals.

We have already seen the effect of tracing the path of a rational that lies beyond the scope of the current tree level: for example, try searching for \(\frac{10}{7}\) in a level 4 Stern-Brocot Tree. The path traced by any number on the Farey and Stern-Brocot Trees provides an increasingly accurate approximation for the given value, whether rational or irrational. (The path listing for Calkin-Wilf does not offer such an approximation, but rather a listing of each "ancestor" back through the generations!) We have limited our tree levels to 10 - sufficient to give very good approximation for any numbers of interest. Try \(\pi\), Euler's number e, the Golden Ratio \(\phi\) and, of course, \(\sqrt(2)\).

Hide

 

 

---

 

Hide Explore

Index

Jump to MathBox

 

---

---

Show

Test Yourself

Index

Jump to MathBox

Share Your Results

 

---

 

From Number to Continued Fraction - cfQuiz1()

From Continued Fraction to Number - cfQuiz2()

Choose cfQuiz1 or cfQuiz2 - cfQuiz()

 

---

 

From Fraction Tree Number to Fraction - ftreeQuiz1()

From Fraction to Fraction Tree Number - ftreeQuiz2()

Choose ftreeQuiz1 or ftreeQuiz2 - ftreeQuiz()

From Fraction to Complete SB Tree - cf2tree()

 

---

 

Matrix Multiplication - mquiz()

Hide Tests

Index

Jump to MathBox

Share Your Results

 

---

---

Show

Mathematical ToolBox

Index

Jump to MathBox

\(f\)

\(f(x)\)

More MathBoxes

---

 

\(g\)

\(g(x)\)

\(h\)

\(h(x)\)

RESET
ALL Numeric
ToolKit CAS
ToolKit Play
♬

Graph Table Steps Axes TextBoxes Sliders

---

---

Index

This document requires an HTML5-compliant browser.

\(a = \)					▶
		-1	5	1
\(b = \)					▶
		-1	5	1
\(c = \)					▶
		-1	5	1
\(d\)				▶
	-1	0	5
\(e\)				▶
	-1	0	5

App generated by GXWeb

Index

Jump to MathBox

Show More Tools

 

---

---

 

Show Spreadsheet

Continued Fraction Spreadsheet Explorer

This browser-based spreadsheet uses the handsontable JavaScript library.

 

43/30 Phi Pi Pi+ e e+

Show/Hide Convergents Plot

Hide Spreadsheet

Back to Top

Jump to MathBox

 

---

WolframAlpha: CAS+

Show Wolfram Alpha

Sometimes, to deal with those stubborn, hard to reach problems, you need something stronger! The powerful Wolfram Alpha online CAS engine will answer almost anything you care to ask - within reason! From the continued fraction of pi to Solve x^2=x+1 to the population of Australia!

Hide Wolfram Alpha

   

---

 GeoGebra Quick CAS

Show GeoGebra

GeoGebra offers another fast and accurate CAS alternative. Use the button above ⇑ for quick computation, or you may like to explore the full GeoGebra web app. ⇒

Hide GeoGebra

Timing: Key Signature:

Play ♬

Switch Views: notes <=> frequencies

Index

Jump to MathBox

Hide More Tools

Hide ToolKit

---

 

---

---

Show

GXWeb Fraction Trees Model

Index

Jump to MathBox

 

---

 

Hide

Index

Jump to MathBox