GXWeb Farey Numbers, Fraction Trees and Kissing Circles

 

---

---

 

Show

Explore Further

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

Exploration 1: Suppose you wanted to know the next term of the sequence between two values, \(\frac{a}{b}\) and \(\frac{c}{d}\)?

Easy! Just add the numerators and the denominators! \(\frac{a+c}{b+d}\). The resulting fraction is called the mediant of \(\frac{a}{b}\) and \(\frac{c}{d}\).

 

---

 

Exploration 2: What do you notice when you cross-multiply numerators and denominators of pairs of Farey neighbours? (If \(\frac{a}{b}\) and \(\frac{c}{d} \)are consecutive terms of a Farey Sequence, consider \(b\cdot c\) and \(a\cdot d\)...)     Exploration 3: AND... If you plot the numerators against the denominators of a Farey Sequence, then you get the amazing Farey Starburst!

Tap to explore the Farey Starburst

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

---

---

 

Show

Continued Fractions and Farey Neighbours

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

There are some wonderful connections between continued fractions and Farey neighbours. 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...

Try Your Own Continued Fractions

 

---

---

 

Hide

Climb Around the Farey (Stern-Brocot) Tree

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

In addition to the Farey Sequence, there are other beautiful ways to display the rationals, 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}\)

\[\frac{0}{1}\]

\[\frac{1}{1}\]

\[\frac{0+1}{1+1}\]\[\frac{1}{2}\]

\[\frac{0+1}{1+2}\]\[\frac{1}{3}\]

\[\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 or 0). To form the continued fraction(s), simply add another 0 or 1 (it does not matter which because both deliver correct but slightly different results). So for \(\frac{1}{2}\), we could add 0 or 1. Begin your continued fraction with zero (or L since all our fractions - for now! - lie between 0 and 1) and then count each repeated element. Then adding 0 will give the continued fraction \([0, 2]=0+\cfrac{1}{2}\) and adding 1 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 (or 00). Add another 0 to get (\([0,3]\)) or 1 for (\([0,2,1]\)). For \(\frac{2}{3}\) from \(\frac{1}{1}\), step LR (or 01). Add another 1 to get (\([0,1,1,1]\)) or 0 to get (\([0,1,2]\)).

Any continued fraction ending in 1 can be compacted by adding that trailing one to the previous term.

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

\[\frac{0}{1}\]\[[0]\]

\[\frac{1}{1}\]\[[1]\]

\[\frac{1}{2}\]\[L+L\]\[[0,2]\]\[L+R\]\[[0,1,1]\]

\[\frac{1}{3}\]\[LL+L\]\[[0,3]\]\[LL+R\]\[[0,2,1]\]

\[\frac{2}{3}\]\[LR+R\]\[[0,1,2]\]\[LR+L\]\[[0,1,1,1]\]

Hide the Farey Tree

 

---

 

Show

Follow a Binary Path to Continued Fractions

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

Next, we 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.

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

\[\frac{0}{1}\]\[[0]\]

\[\frac{1}{1}\]\[[1]\]

\[\frac{1}{2}\]\[L+L\]\[[0,2]\]\[L+R\]\[[0,1,1]\]\[(1)\]

\[\frac{1}{3}\]\[LL+L\]\[[0,3]\]\[LL+R\]\[[0,2,1]\]\[11\]\[(3)\]

\[\frac{2}{3}\]\[LR+R\]\[[0,1,2]\]\[LR+L\]\[[0,1,1,1]\]\[10\]\[(2)\]

\[\frac{1}{4}\]\[LLL+L\]\[[0,4]\]\[[0,3,1]\]\[111\]\[(7)\]

\[\frac{2}{5}\]\[LLR+R\]\[[0,2,2]\]\[[0,2,1,1]\]\[110\]\[(6)\]

\[\frac{3}{5}\]\[LRL+L\]\[[0,1,1,2]\]\[[0,1,1,1,1]\]\[101\]\[(5)\]

\[\frac{3}{4}\]\[LRR+R\]\[[0,1,3]\]\[[0,1,2,1]\]\[100\]\[(4)\]

\[\frac{1}{5}\] LLLL+L [0,5] 1111 (15)

\[\frac{2}{7}\] LLLR+R [0,3,2] 1110 (14)

\[\frac{3}{8}\] LLRL+L [0,2,1,2] 1101 (13)

\[\frac{3}{7}\] LLRR+R [0,2,3] 1100 (12)

\[\frac{4}{7}\] LRLL+L [0,1,1,3] 1011 (11)

\[\frac{5}{8}\] LRLR+R [0,1,1,1,2] 1010 (10)

\[\frac{5}{7}\] LRRL+L [0,1,2,2] 1001 (9)

\[\frac{4}{5}\] LRRR+R [0,1,4] 1000 (8)

\[\frac{1}{6}\] (31)

\[\frac{2}{9}\] (30)

\[\frac{3}{11}\] (29)

\[\frac{3}{10}\] (28)

\[\frac{4}{11}\] (27)

\[\frac{5}{13}\] (26)

\[\frac{5}{12}\] (25)

\[\frac{4}{9}\] (24)

\[\frac{5}{9}\] (23)

\[\frac{7}{12}\] (22)

\[\frac{8}{13}\] (21)

\[\frac{7}{11}\] (20)

\[\frac{7}{10}\] (19)

\[\frac{8}{11}\] (18)

\[\frac{7}{9}\] (17)

\[\frac{5}{6}\] (16)

Tap on any table cell above for more

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

Test Yourself

1. What fraction lies at the end of the path LLRR(+R) (or LLRR(+L))? (Tap for the answer)

2. What fraction has continued fraction [0, 1, 1, 1, 2] (or [0, 1, 1, 1, 1, 1])? (Tap for the answer)

3. What do you notice about the sums of each continued fraction on the same row? (Tap for the answer)

4. What do you notice about the numerators of the fractions across each row? (Tap for the answer)

5. What about the denominators of each fraction across each row? (Tap for the answer)

6. What fraction occupies position 40 on the Farey Tree? (Tap for the answer)

Hide the Binary Tree

 

---

 

Show

Explore the Stern-Brocot Tree

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

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.

Try some Stern-Brocot values yourself!

Perhaps most remarkably, the Stern-Brocot Tree has its own continued fraction! (With full credit 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)].)

Alternatively, it appears that the Stern-Brocot continued fraction CAN be expressed as a simple continued fraction by setting each 1 term to -1. Hence, the extended form for order 3 (including both left and right branches) could be expressed as \[[0,3,-1,3,-1,5,-1,3,-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}\]

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

---

 

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.

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

---

 

Show

Explore the Calkin-Wilf Tree

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

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

\(\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}\)...

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

{b(n)}_n≥0 = {1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,...}.

This is a bit remarkable - at very least, for its efficiency. This single list can be viewed in (at least) three ways:

• As the list of numerators of the Calkin-Wilf Tree,

• As the list of denominators of the Calkin-Wilf Tree (after removing the first term) OR

• As the actual list of fractions of the Calkin-Wilf Tree by taking each term with its next term!

Differing from the Stern-Brocot tree above, the rationals between 0 and 1 are paired (interleaved) with their reciprocal complements.

Perhaps even simpler than Stern-Brocot, any term of the Calkin-Wilf tree can directly reveal its continued fraction through the binary form of the term number!

Consider the 19th term of the Calkin-Wilf tree: 19 = 10011 (binary) - RLLRR (counting from zero).

For Calkin-Wilf, count repeated terms FROM THE RIGHT to get the continued fraction.

If the binary ends in zero (i.e. if the term is even) then add a zero as the first term - even term values always lie between 0 and 1!

Calkin-Wilf: term 19

• => [2,2,1]

• => \(\frac{7}{3}\)

Try some Calkin-Wilf values yourself!

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

 

---

 

Climb further around the Farey Tree

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

---

---

 

Show

Descartes Kissing Circles Theorem

Descartes (Kissing Circles) Theorem describes a beautiful and perhaps surprising relationship between tangential circles: in general, for any three circles tangent to each other, two other circles exist (one inner and the other bounding the three) and all are related by a quadratic equation. This relationship is described most easily in terms of the curvature of each circle, where curvature is defined as the reciprocal of the radius.

If the circles have curvature a, b, c and x, then

\[(a+b+c+x)^2 \]\[= 2\cdot (a^2 + b^2 + c^2 + x^2)\]

A little rearrangement allows us to find the curvature (and hence, radius) of the inner and outer tangent circles given any three (here the greater of the two solutions describes the curvature of the inner circle and the lesser value (possibly negative) relates to the outer bounding circle):

\[x = a + b + c \]\[\pm \sqrt{(a\cdot b + a\cdot c + b\cdot c)}\]

Of particular interest here is the special case where one of the three circles has infinite radius (and hence zero curvature) - i.e. one of the circles is a straight line, with the other two circles tangent to it and to each other. This case (⇒) may serve to define Ford Circles and the next Ford Circle between two tangent circles with curvatures a and b will have curvature (derived from the above equation): \[c = a + b + 2\cdot \sqrt{(a\cdot b)}\]

Here it is interesting to note that, when used to represent the rational numbers in the Farey Sequence, the radius of the Ford Circle standing on the rational value \(\frac{a}{b}\) is \(\frac{1}{2\cdot b^2}\). The centre of such a Ford Circle is \((\frac{a}{b},\frac{1}{2\cdot b^2})\).

You might check that this holds for the model above and then explore the values for other circle groupings!

Learn More about Kissing Circles

Try the Kissing Circles Jigsaw

Hide Descartes

Back to Top

Jump to Model

Math Toolkit

Jump to GXWeb

 

---

---

 

Show QR

Share with QR Code

Back to Top

Jump to Model

Math Toolkit

Explore Further

Jump to GXWeb

Geometry Expressions Showcase

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 Geometry Expressions Showcase, but you can use it as an alternative to sending your assessment data via email, web or Google Cloud. You can even use it to send your own messages! Send Your Own QR Code Reset QR Code

 

---

---

 

Show

Construct your own Model with GXWeb

Back to Top

Jump to Model

Math Toolkit

Explore Further

Jump to GXWeb

Hide GXWeb

 

---

---

 

Show

Behind the Scenes

Back to Top

Jump to Model

Math Toolkit

Explore Further

Jump to GXWeb

 

Learn How: Create your own GXWeb Assessment Task

Learn How 2: Take GXWeb to the Next Level

View JavaScript Task Code (fareygx.js)

View JavaScript GXWeb Code (gxfarey.js)

View JavaScript Shared Code (latex2math.js)

View JavaScript Shared Code (sharedcodend.js)

Back to Top

Jump to Model

Math Toolkit

Explore Further

Jump to GXWeb

---

---

 

©2021 Compass Learning Technologies ← Live Mathematics on the Web ← Geometry Expressions Showcase ← GXWeb Farey Numbers, Fraction Trees and Kissing Circles