©2022 Compass Learning Technologies ← GXWeb Jigsaws and Quizzes ← GXWeb Fractured Fractions → GXWeb Fractured Fractions Collection
GXWeb Fractured Fractions Collection
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
An Introduction to Continued Fractions by Dr Ron Knott
Chaos in Numberland: The secret life of continued fractions by John D. Barrow
Explore Bill Gosper (1972): Continued Fraction Arithmetic
Calkin and Wilf (1999): Recounting the Rationals
Bruce Bates (2014): The Stern-Brocot Continued Fraction
Bates, B., Bunder, M. and Tognetti, K. (2010): Linking the Calkin–Wilf and Stern–Brocot trees
With thanks to the late 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?
Then dig deeper into Continued Fractions.
More to Explore - the Continued Fractions Collection ⇓
Drag point P or use the INPUT button to explore
different numbers and their continued fractions.
Press JIGSAW to try the Continued Fraction JigSaw.App generated by GXWeb
\[ \frac{10}{7} = [1,2,3]\]
\[ ⇒ 1 + \frac{1}{2 + \frac{1}{3}}\]
\[ \approx 1.4285714286\]
Introduction
If you have not come across continued fractions in your mathematical travels, then it is high time you did!
Every real number, rational and irrational, can be represented as a continued fraction. While normal fractions can only represent rational numbers, continued fractions are different - full of surprising patterns and relationships.
Not surprisingly, rational numbers produce finite continued fractions, while irrationals become infinite continued fractions.
107107=1+37=1+37=1+173=1+173=1+12+13=1+12+13
Unlike irrational decimals, however, even irrational continued fractions can be predictable and are an ideal way to calculate approximate values - as accurately as you like!
Continued fractions have many practical applications but one of the most important lies in their ability to offer VERY good approximations to irrational numbers - the more convergents, the better the approximation. Indeed, each convergent gives the Best Approximation of the First Kind (look that up!) AND if a large value turns up in the list, then cutting the continued fraction just before that large value gives an extremely accurate approximation!
Study the examples which follow and see what you notice.
Some Examples
The Golden Ratio (or Golden Mean) (1 + sqrt(5))/2: 1+√521+√52
ϕ≈1+11+11+11+11+⋯ϕ≈1+11+11+11+11+⋯
Tap above or enter \phi in the MathBox below and press the f(x) button), OR for another approach, think of this continued fraction as x=1+1x=>x2=x+1x=1+1x=>x2=x+1
EXPLORE: Can you see why 1+√2=(2+√82)1+√2=(2+√82) is called the silver mean and 3+√1323+√132 is the bronze mean? What would be their quadratic equations? Any suggestions for copper, nickel, aluminium or other metallic means?
Sqrt(2) ⇒ √2≈1+12+12+12+12+⋯√2≈1+12+12+12+12+⋯
Tap above or enter \sqrt(2) in the MathBox below and press the f(x) button) - or try x=1+11+x=>x2=2x=1+11+x=>x2=2
EXPLORE: Can you find the quadratic equation form for √(3)√(3) or √(5)√(5)?
Pi ⇒ π≈3+17+115+11+1292+⋯π≈3+17+115+11+1292+⋯
(Tap above or enter \pi in the MathBox below and press the f(x) button) (but no closed form equation for this one!)
Continued fractions do come in more than one flavour.
In most cases, we deal with SIMPLE continued fractions, for which the numerators are all equal to 1, as shown above.
The famous Indian mathematician, Srinivasa Ramanujan, along with Euler, Gauss and other greats over many years have been fond of far more interesting varieties - visit GXWeb Fractured Functions to learn more about these amazing creatures.
π≈41+123+225+327+429+5211+6213+⋯π≈41+123+225+327+429+5211+6213+⋯
e≈3−14−25−36−47−58−69+⋯e≈3−14−25−36−47−58−69+⋯
Continued fractions continue to be a source of research in many branches of mathematics. Use the tools available here to explore these wonderful mathematical opportunities!
You might notice that while simple continued fractions give predictable values for only a limited range of real numbers (the so-called Quadratic Irrationals), examples like these show that even the most transcendental of numbers can be expressed in predictable form. Observe, below, that continued fractions can also be expressed as the product of matrices!
Mathematics has been described as a search for patterns and relationships. What patterns and relationships did you find in these few examples? Use the tools which follow to explore your ideas further, and take a few moments to answer the questions that follow.
Once you have finished the questions, feel free to come back and continue to play with and learn more about these extraordinary numbers. They can be a gateway to interesting and important topics in mathematics, nature and computing.
Explore the Magic Table
Introduction: What is a Magic Table?
To convert a real number to a continued fraction is easy! Try this yourself?
But what if you want to go in the other direction? If you have a continued fraction, and would like to know the real number that it represents?
For some rational numbers (and approximations of irrationals), this is (relatively) easy, since the continued fraction is finite. For most, though, it can be quite arduous.
The most commonly used method involves starting from the bottom and working upwards. This approach, however, does not reveal the successive approximations, the convergents, which in many cases may be just as useful as the final result.
\[ \frac{10}{7}\]\[= 1+\frac{3}{7}\]\[= 1 + \frac{1}{\frac{7}{3}}\]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3}} \]\[= [1,2,3]\]
\[ [1,2,3]\]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3}} \]\[= 1 + \frac{1}{\frac{7}{3}}\]\[= 1+\frac{3}{7} \]\[= \frac{10}{7} \]
Alternatively, you might try the Magic Table method!
The magic table 1, 2 (first described by Gosper (1972) - credit for the name goes to Associate Professor Terry Gagen of the University of Sydney) offers an efficient and (relatively) simple way to generate the convergents of a continued fraction - it can even be used, in 1 or 2 dimensions, on linear fractional transformations of continued fractions and, in 3 dimensions, forms the basis for Gosper's algorithm for continued fraction arithmetic.
For example, the continued fraction of
\[\sqrt(37) => \]\[a(n) = [6,12,12,12,12,12,12,...]\]\[b(n) = [1,1,1,1,1,1,1...]\] \[6 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12... }}}}}}}\]Using the approaches described here is much simpler than, for example, matrix methods to calculate a result such as
\[\frac{\sqrt{37} + 4}{7} = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \sqrt(37) = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \begin{bmatrix} \sqrt(37) && 0 \\ 0 && 1 \end{bmatrix} \]where the linear fractional transformation is the matrix
\[\begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \ and \ \begin{bmatrix} 1 && 0 \\ 0 && 1 \end{bmatrix}\]represents the identity matrix.
\[...\] \[12\] \[12\] \[12\] \[12\] \[12\] \[6\] \[a(n)\] \[...\] \[1\] \[1\] \[1\] \[1\] \[1\] \[(1)\] \[b(n)\] \[...\] \[213442\] \[17665\] \[1462\] \[121\] \[10\] \[1\] \[4\] \[...\] \[148183\] \[12264\] \[1015\] \[84\] \[7\] \[0\] \[7\]
Introducing the Magic Table: Dimension 1
Gosper's original (dimension 1) version of the magic table was presented horizontally, reading from right to left. A simplified form (which delivers each convergent in turn) might be represented as shown above.
Note that Gosper dealt only with simple continued fractions for which all b(n) (numerator) terms may be assumed to be 1. We go a step further here, adding a b(n) row to support general continued fractions.
Can you see how the pairs of numbers below the continued fraction terms are calculated? (Notice that the first convergent is calculated directly from the terms of the linear fractional transformation.)
Tap on these pairs to see, or tap on the red continued fraction terms - from right to left - to see Gosper's Magic Table in action!
Introducing the Magic Table: Dimension 2
More importantly, Gosper was not really interested in simply outputting the convergents of continued fractions.
His real goal was to take a continued fraction, operate on it in some way - initially, using a linear fractional transformation, but leading to arithmetic operations with another continued fraction - and output the result directly as a continued fraction: true continued fraction arithmetic!
For this, he needed more dimensions for his magic table!
Teasing Out the Resultant Continued Fraction
It should be noted that drawing out each term of the resultant continued fraction is not always a straightforward operation.
Consider the first TWO convergents of
\[\frac{\sqrt{37} + 4}{7} = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \sqrt(37)\] \[=> \frac{10}{7} \ and \ \frac{121}{84}\]Taking the floor or integer part of both delivers the same result (\(|\frac{10}{7}| = |\frac{121}{84}| = 1\)), so we can be confident in the first term of our resultant continued fraction.
To continue, we need the dimension 2 table, since we now move one step down and one step to the left (in the table above, or to the right in the table below). The next two convergents to consider are \(\frac{84}{37}\) and \(\frac{1015}{447}\). If the floor values of both agree (which they do in this case), we continue this process, moving down and horizontally forward.
If NOT, then we simply move one step horizontally forward, and try the next pair of convergents, until we find two that agree, and this process gives each subsequent term of our resultant continued fraction.
For a more interesting example, consider Gosper's case of \(e\) with linear fractional transformation, [1,-1,1,1]:
\[tanh(\frac{1}{2}) = \frac{e-1}{e+1}\]Here we see that the first convergent pair (\(\frac{1}{3}\) and \(\frac{2}{4}\)) both deliver floor values of 0. The second pair (\(\frac{11}{5}\) and \(\frac{4}{2}\)) give us the next resultant term of 2.
Subsequently, though, \(|\frac{5}{1}| = 5\) and \(|\frac{7}{1}| = 7\). We must continue to the next terms, \(\frac{12}{2}\) and (with a little calculation) \(\frac{55}{9}\) (\(4 \cdot 12 + 1 \cdot 7 = 55\) and \(4 \cdot 2 + 1 \cdot 1 = 9\)) to confirm the floor result of 6.
The floor values of pairs of adjacent convergents must differ by no more than 1 to deliver the next term of the resultant continued fraction.
For ease of presentation, in our versions, the terms are displayed vertically, with the terms of the linear fractional transformation found at the top of the numerator and denominator columns (rotated -90°).
Step by Step
Tap to view:
Simple Convergent Form 1
Simple Convergent Form 2
Gosper Magic Table 1
Gosper Magic Table 2
Gosper Magic Table 3
Gosper Magic Table 4
Gosper Magic Table 5
In its simplest form, Gosper's Magic Table initially offers a convenient way to generate the convergents for a given continued fraction, along with a linear fractional transformation, expressed as a 2x2 matrix.
(Tap for an example) ⇑
General Continued Fractions: Some Examples
Note that the Magic Table presented here represents an extension of Gosper's method, supporting general continued fractions in addition to simple ones. For example, did you know that
\[\pi \approx 0 + \cfrac{4}{1 + \cfrac{1}{3 + \cfrac{4}{5 + \cfrac{9}{7 + \cfrac{16}{9 + \cfrac{25}{11 + \cfrac{36}{13 + \cfrac{49}{15 + \cfrac{64}{17 + \cfrac{81}{19...}}}}}}}}}}\]\[a(n) = [0,1,3,5,7,9,11,13,15,17,19]\]\[b(n) = [4,1,4,9,16,25,36,49,64,81]\]
And what about the Farey and Stern-Brocot Continued Fractions: if you wanted to start a list of every rational number, then these amazing continued fractions are perfect for that!
\[0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}} = 0 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1}}}}\] \[⇒ [0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1]\]
Farey Sequence Level 3:mtable([[0,3,-1,3,-1],[1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,3,1,3,1],[1,-1,-1,-1,-1]],[1,0,0,1])
\[0 + \cfrac{1}{4 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}\] \[⇒ [0,\frac{1}{4}, \frac{1}{3}, \frac{2}{5},\frac{1}{2}, \frac{3}{5}, \frac{3}{4}, \frac{2}{3},1]\] Farey Sequence Level 4:
mtable([[0,4,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,4,1,3,1,5,1,3,1],[1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])
\[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}}}}}}}}\] \[⇒ [0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1,\frac{3}{2},\frac{2}{1}, \frac{3}{1},\frac{1}{0}]\] Stern-Brocot Sequence Level 3:
mtable([[0,3,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,3,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])
Stern-Brocot Sequence Level 4:
\[0 + \cfrac{1}{4 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{7 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}}}}}}}}}\] \[⇒ [0,\frac{1}{4}, \frac{1}{3}, \frac{2}{5},\frac{1}{2}, \frac{3}{5}, \frac{3}{4}, \frac{2}{3},1, \frac{3}{2}, \frac{4}{3}, \frac{5}{3},\frac{2}{1}, \frac{5}{2}, \frac{3}{1}, \frac{4}{1}, \frac{1}{0}]\]mtable([[0,4,-1,3,-1,5,-1,3,-1,7,-1,3,-1,5,-1,3],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]],[1,0,0,1],0,17)
OR mtable([[0,4,1,3,1,5,1,3,1,7,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1],0,17)
Try More Examples
Simple (Convergent)
Magic Table
Dimension 1Gosper
Magic Table
Dimension 2Enter mtable(), or
mtable(sqrt(37)), or
mtable(sqrt(37),[1,4,0,7]), or even
mtable(sqrt(37),[1,4,0,7],0,12)Try one of Gosper's examples:
mtable(sqrt(2),[0,2,-1,3],0,12)You can also enter arrays: mtable([1,2,3,4,5],[1,0,0,1],0,12) or
mtable([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)Try mtable([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)
Enter gmt(), or
gmt(sqrt(37)), or
gmt(sqrt(37),[1,4,0,7]), or even
gmt(sqrt(37),[1,4,0,7],0,12)Try one of Gosper's examples:
gmt(sqrt(2),[0,2,-1,3],0,12)You can also enter arrays: gmt([1,2,3,4,5],[1,0,0,1],0,12) or
gmt([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)Try gmt([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)
mtable([[0,1,3,5,7,9,11,13,15,17,19],[4,1,4,9,16,25,36,49,64,81,100]],[1,0,0,1],0,12).
Perhaps even compare
mtable([[4,2,2,2,2,2,2,17,294],[-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1]) with
mtable([[4,-2,2,-2,2,-2,2,-17,294],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])?
Build Your Own Continued Fraction
To convert a real number (n) to a continued fraction is easy!
Try this yourself?
Step 1: Take the integer part of the number - floor[n] or Math.floor(n): This is your first index (call it a0a0), and first convergent.
Step 2: Subtract the integer part to leave the decimal part - the tail. Tail=n−floor(n)Tail=n−floor(n)
Step 3: Calculate the reciprocal of the tail (1Tail1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the integer part of this reciprocal value (a1=floor(1Tail)a1=floor(1Tail)): This is your next index - call it a1a1, and a0+1a1a0+1a1 the next convergent.
Step 5: Return to Step 2 and repeat the process...
But what if you want to go in the other direction? If you have a continued fraction, and would like to know the real number that it represents?
For rational numbers, this is easy, since the continued fraction is finite.
The most commonly used method involves starting from the bottom and working upwards.
Alternatively, try the Magic Table!
For most irrationals, finding the real number represented by a continued fraction is much harder, but not for quadratic irrationals, which are periodic.
Study the examples above for the golden ratio and the square root of 2. For any periodic continued fraction, we need to isolate the periodic part and use this to form a quadratic equation. For example...
[1,2,3,1,2,3,1,2,3...]=1+12+13+11+12+13+...[1,2,3,1,2,3,1,2,3...]=1+12+13+11+12+13+... x=1+12+13+1xx=1+12+13+1x
Mathematical ToolBox
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?
f(x)f(x)
g(x)g(x)
h(x)h(x)
a=a= -1 5 1 b=b= -1 1 5 c=c= -1 1 5
Continued Fraction Spreadsheet Explorer
This browser-based spreadsheet uses the handsontable JavaScript library.
WolframAlpha: CAS+
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!
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. ⇒
More to Explore: the Continued Fractions Collection
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 34213421, 55345534 and 89558955. 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+1x=>x2=a⋅x+1=>(a+√(4+a2)2x=a+1x=>x2=a⋅x+1=>(a+√(4+a2)2 and the noble numbers: x=a+11−a+x=>(2⋅(x−a)+1)2=5=>(√(5)+2a−1)2x=a+11−a+x=>(2⋅(x−a)+1)2=5=>(√(5)+2a−1)2.
Negative (or Reversal) Continued Fractions
Before considering general continued fractions, a note about the continued fractions of negative numbers.
107=[1,2,3]=1+12+13107=[1,2,3]=1+12+13Begin by observing that
−107≠−1−1−2−1−3(=−25)−107≠−1−1−2−1−3(=−25)AND
−107≠1−12−13(=25)−107≠1−12−13(=25)However
−107=[−1,−2,−3]=−1+1−2+1−3−107=[−1,−2,−3]=−1+1−2+1−3and (perhaps surprisingly?)
107=[2,2,4]−=2−12−14107=[2,2,4]−=2−12−14
Did you know that there are TWO classical forms for continued fractions? I only found this out recently.
The simple or general form is built by taking the floor (or whole number part) of the fraction at each level and adding the reciprocal of the tail.
To convert a real number (n) to a continued fraction is easy!
The reversal or negative form takes instead the ceiling or next whole number value above, and subtracts the value of the term to form the tail! The reciprocal of this tail then forms the next term in the process.
To convert a real number (n) to a negative or reversal continued fraction is just as easy!
Try this yourself?
Step 1: Take the integer part of the number - floor[n] or Math.floor(n): This is your first index (call it a0a0), and first convergent.
Step 2: Subtract the integer part to leave the decimal part - the tail. Tail=n−floor(n)Tail=n−floor(n)
Step 3: Calculate the reciprocal of the tail (1Tail1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the integer part of this reciprocal value (a1=floor(1Tail)a1=floor(1Tail)): This is your next index - call it a1a1, and a0+1a1a0+1a1 the next convergent.
Step 5: Return to Step 2 and repeat the process...
Try this yourself?
Step 1: Round up to the integer above the number - ceil[n] or Math.ceil(n): This is your first index (call it a0a0), and first convergent.
Step 2: Subtract the current value from the integer part to leave the decimal part - the tail. Tail=ceil(n)−nTail=ceil(n)−n
Step 3: Calculate the reciprocal of the tail (1Tail1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the ceiling of this reciprocal value (a1=ceil(1Tail)a1=ceil(1Tail)): This is your next index - call it a1a1, and a0+1a1a0+1a1 the next convergent.
Step 5: Return to Step 2 and repeat the process...
107=[1,2,2,1]107=[1,2,2,1]=1+12+12+11=1+12+12+11 (Enter 10/7 or 1,2,3 or 1,2,2,1)
[107]−=[2,2,4]−[107]−=[2,2,4]−=2−12−14=2−12−14 (Enter [10/7]^- or [2,2,4]^-
or [10/7]{neg} or [2,2,4]{neg})4330=[1,2,3,4]4330=[1,2,3,4]=1+12+13+14 (Enter 43/30 or 1,2,3,4)
[4330]−=[2,2,5,2,2,2]−=2−12−15−12−12−12 (Enter [43/30]^- or [2,2,5,2,2,2]^-
or [43/30]{neg} or [2,2,5,2,2,2]{neg})Try a few more examples and see if you can see a pattern...
HINT: It helps if your simple continued fraction form has an EVEN number of terms!
Converting to the Negative Form
With thanks to Morier-Genoud and Ovsienko (2019)
Let r and s be two coprime positive integers, and assume that r>s. The rational number rs has unique expansions
rs=a1+1a2+1a3+1...a2m =c1−1c2−1c3−1...ckwhere ai≥1 and ci≥2 for all i. The first is called a simple continued fraction and the second, a negative or reversal continued fraction.
Note that we can always assume a simple continued fraction has an even number of terms since every such continued fraction can be expressed in both a compact form (with last term not equal to 1) and an expanded form:
[a1,a2,...,an]=[a1,a2,...,an−1,1]Then the terms of a negative or reversal continued fraction may be derived from those of the equivalent simple form as follows:
[c1,c2,c3,...,ck−1,ck]= [a1+1,2 (repeated a2−1 times)...,a3+1,2 (repeated a4−1 times)...,a2m−1+1,2 (repeated a2m times)]
Negative Terms in a Continued Fraction
As noted by Knott, LaGrange points out that it is a simple matter of algebra to show that we can remove subtractions in favour of addtions.
Wherever there is a subtraction, "push" it into the rest of the CF making positive numbers into negatives. We use C to represent the rest of a CF which may be empty or consist of one or more terms:
a−1b+C=a+−1b+C=a+1−b−CThen if
C=1c+1d+1e+...note that a negative value in a numerator ONLY changes the signs of the subsequent pair of numerator and denominator - this then flows on through the remaining terms to deliver an equal result without requiring any further sign changes.
a−1b+1c+1d+1e+... =a+−1b+1c+1d+1e+... =a+1−b−1c+1d+1e+... =a+1−b−1c+1d+1e+...Observe from the linked example that this holds for any occurrence within the terms of the continued fraction.
And for a pair of consecutive negative numerators?
a+1b−1c−1d+1e+... =a+1b+−1c+−1d+1e+... =a+1b+1−c+1d+1e+...Simpler still!
Each consecutive pair of negative numerator values results in just a single negative leading term (denominator) in the second level. All other negative values cancel.
A string of sequential negative numerators, then, will result in alternating positive and negative leading terms.
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...
Simple Quadratic Continued Fractions
More Quadratic Continued Fractions
Euler's Numbers (ex)
Euler's Numbers (log(1+xy))
Pieces of Pi
Not So AbSurd After All
Continued Fractions Arithmetic
Continued Logarithms
x2=m
x2=a2+b
x2−a2=b
(x−a)(x+a)=b
x−a=ba+x
x=a+ba+x
Some Matrix Fraction Magic
As seen already, continued fractions can be represented in matrix form, offering some interesting possibilities - and applicable to both simple and generalised continued fractions.
1. Continued Fraction Matrices
The most-commonly documented approach involves the product of 2 x 2 matrices.
a0+b0a1+b1a2+b2a3+b3a4...=[a0b010]⋅[a1b110]⋅[a2b210]⋅[a3b310]⋅[a4110]...
For example, arithmetic operations can be readily expressed.
[1,2,3,1,2,3,1,2,3,1...]=>1+12+13+11+12+13+11...[1110]⋅[2110]⋅[3110]⋅[1110]⋅[2110]⋅[3110]⋅[1110]... x=1+12+13+1x=4+√(37)7 If...√37=6+112+112+112+112+...=>[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]... Then...4+√(37)7=[1407]⋅√37=>[1407]⋅[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]...Even less predictable ones:
[2,2,3,1,1,2,3,1,1,2,3...]=>2+12+13+11+11+12+13... [2110]⋅[2110]⋅[3110]⋅[1110]⋅[1110]⋅[2110]⋅[3110]... x−1=1+12+13+11+1x−1x−1=1+12+13+x−1x=4+√(11)3 If...√11=3+13+16+13+16+...=>[3110]⋅[3110]⋅[6110]⋅[3110]⋅[6110]... Then...4+√(11)3=[1403]⋅√11=>[1403]⋅[3110]⋅[3110]⋅[6110]⋅[3110]⋅[6110]...
2. Tridiagonal Matrix Continued Fractions
Two alternative approaches involve larger square (tridiagonal) matrices. (eg Frommer, Kahl and Tsolakis (2021) and Qi, Wen Guo and Lim (2020))
Let M=[a0b0000−1a1b1000−1a2b2000−1a3b3000−1a4]Then taking the inverse of M, the first ([1,1]) term gives the reciprocal of the final convergent of the continued fraction:
1inv(M)[1,1]=a0+b0a1+b1a2+b2a3+b3a4A second approach involves the determinants of two square matrices, p and q as follows:
a0+b0a1+b1a2+b2a3+b3a4=det(p)det(q)
p=[a0b0000−1a1b1000−1a2b2000−1a3b3000−1a4] q=[a1b100−1a2b200−1a3b300−1a4]
Some expected relationships...
And even some unexpected ones!
Tap on the matrix examples above and follow the directions. Then just press h (at the end, you may need to press the TextBoxes button to lay out the result correctly).
3. Matrix as Mediant: Building the Stern-Brocot Tree
Returning to 2 x 2 matrices, we find another surprisingly simple and powerful matrix approach to building the Stern-Brocot Tree (van der Poorten and Wildberger), and consequently, listing all possible rationals.
We begin by viewing 2 x 2 matrices in a new way, defining the mediant:
[abcd]=>ac⊕bd=a+bc+dThen the familiar identity matrix becomes
[1001]=>10⊕01=1+00+1=11Now we define two matrices, which will serve as left (L) and right (R) steps for our tree:
L=[1011] and R=[1101]Then any term of our Stern-Brocot Tree can be represented by a matrix
M=[abcd]with parents ac and bd and determinant 1. Such a matrix can serve as the parent for two further matrices:
M⋅L=[abcd]⋅[1011] and M⋅R=[abcd]⋅[1101] M⋅L=[a+bbc+dd] and M⋅R=[aa+bcc+d] M⋅L=>a+2⋅bc+2⋅d and M⋅R=>2⋅a+b2⋅c+d
Beginning with our identity matrix
M=[1001]=>1+00+1=11Notice the parents of 11 are 01 and 10?
We quickly see the effects of a Left and Right step:
M⋅L=[1001]⋅[1011] and M⋅R=[1001]⋅[1101] M⋅L=[1+00+00+10+1] and M⋅R=[1+01+00+00+1] M⋅L=[1011] and M⋅R=[1101]∗ M⋅L=>1+01+1 and M⋅R=>1+10+1 M⋅L=>12 and M⋅R=>21Line * shows that the parents of 12 are 01 and 11 and the parents of 21 are 11 and 10?
Refer back to the section Building the Fraction Trees to see this process in more detail, and try some for yourself!
See a live demo?
Play more with continued fractions?
Continued Fraction Arithmetic
Contrary to everybody, this self contained paper will show that continued fractions are not only perfectly amenable to arithmetic, they are amenable to perfect arithmetic. (Bill Gosper, 1972)
For Gosper, the appealing concept of perfect arithmetic may well have involved using continued fractions to perform calculations to any desired degree of accuracy. Continued fractions are ideal tools for successive approximation.
The examples explored here may offer a glimpse into one of the enduring questions regarding continued fractions: they are wonderful at representing numbers, both rational and irrational, but can they also serve as practical tools for computation?
While some of these examples involve simple, finite rational values, it is unlikely that anyone would realistically wheel in continued fraction arithmetic for such questions as 107+225.
But for those convoluted rationals and especially those infinite irrationals? Well... it was made for such as these!
Continued Logarithms
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:
f(x)={(x−1)x≥11x0<x<1terminatex=0
Count the number of times we encounter x⇒x−1 before we either reciprocate or terminate. These counts are the terms [a0,a1,...] of our continued fraction.
Continued Logarithms (base b) (Gosper, 1978) are defined in a similar way by
g(x)={xbx≥bb−1x−11<x<bterminatex=1
For x≥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)
19=24+2422+2221+2121 =16+164+42+22
The continued logarithm for 215=>[1,0,1,0,1]cl(3)=>[1,1,1]cl(3)
215=31+2⋅3131+2⋅3131 =3+63+63
Continued Fractions and Farey Trees
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: 01,11.
Next, add those with denominator 2: 01,12,11.
Add those with denominator 3 ( 01,13,12,23,11) 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, 25 and 512 are neighbours in Farey(12), as are 619 and 722 in Farey(25). Check their continued fraction forms and try more of your own...
Climb Around the Farey (Stern-Brocot) Tree
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 01 and 11 give 0+11+1=12
Then 01 and 12 give 0+11+2=13 and 11 and 12 give 1+11+2=23
01 11
0+11+112
0+11+213 1+11+223 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 1n and ends with n−1n.
From 11, to get to 12, 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 12, 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+12 and LR gives [0,1,1]=0+11+11.
In the same way, to get to 13 from 11, step LL. Add another L to get LLL ([0,3]) or LLR ([0,2,1]). For 23 from 11, 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.
01[0] 11[1]
12L+L[0,2]L+R[0,1,1]
13LL+L[0,3]LL+R[0,2,1] 23LR+R[0,1,2]LR+L[0,1,1,1]
Follow a Binary Path to Continued Fractions
Finally, note that every element of our Farey Tree can be allocated its own unique number, starting with 12 as number 1, then stepping down and counting from right to left. This gives 23 as number 2, 13 in position 3 and 34 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 (12) from the starting point of 11 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 79 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 79 we get 97 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.
01[0] 11[1]
12L+L[0,2]L+R[0,1,1](1)
13LL+L[0,3]LL+R[0,2,1]11(3) 23LR+R[0,1,2]LR+L[0,1,1,1]10(2)
14LLL+[0,4][0,3,1]111(7) 25LLR+[0,2,2][0,2,1,1]110(6) 35LRL+[0,1,1,2][0,1,1,1,1]101(5) 34LRR+[0,1,3][0,1,2,1]100(4)
15 LLLL+L
[0,5]
1111
(15)
27 LLLR+R
[0,3,2]
1110
(14)
38 LLRL+L
[0,2,1,2]
1101
(13)
37 LLRR+R
[0,2,3]
1100
(12)
47 LRLL+L
[0,1,1,3]
1011
(11)
58 LRLR+R
[0,1,1,1,2]
1010
(10)
57 LRRL+L
[0,1,2,2]
1001
(9)
45 LRRR+R
[0,1,4]
1000
(8)
16 (31)
29 (30)
311 (29)
310 (28)
411 (27)
513 (26)
512 (25)
49 (24)
59 (23)
712 (22)
813 (21)
711 (20)
710 (19)
811 (18)
79 (17)
56 (16)
Tap on any table cell above for more
Test Yourself
What fraction lies at the end of the path LLRR(+R) (or LLRR(+L))? (Tap for the answer)
What fraction has continued fraction [0, 1, 1, 1, 2] (or [0, 1, 1, 1, 1, 1])? (Tap for the answer)
What do you notice about the sums of each continued fraction on the same row? (Tap for the answer)
What do you notice about the numerators of the fractions across each row? (Tap for the answer)
What about the denominators of each fraction across each row? (Tap for the answer)
What fraction occupies position 40 on the Farey Tree? (Tap for the answer)
Explore the Stern-Brocot Tree
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!
The Stern-Brocot Tree has its own continued fraction! (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)].)
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⋅1+1)? 4 → 5 (2⋅2+1)? But for 6, 2⋅3+1 does not equal 5, and for 8, 2⋅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⋅1 so b = 1 and 2⋅b+1=3.
- 4=2⋅2⋅1 so b = 2 and 2⋅b+1=5.
- 6=2⋅3 so b = 1 and 2⋅b+1=3.
- 8=2⋅2⋅2⋅1 so b = 3 and 2⋅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
↓
b20
↓
021
↓
120⋅3
↓
022
↓
220⋅5
↓
021⋅3
↓
120⋅7
↓
023
↓
320⋅9
↓
021⋅5
↓
120⋅11
↓
022⋅3
↓
120⋅13
↓
021⋅7
↓
120⋅15
↓
02⋅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 aa+b and a+bb iteratively below each fraction ab.
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
11,12,21,13,32,23,31,14,43,35,52,25,53,34,41...
The sequence has the property that each denominator is the next numerator. That means that the nth rational number in the list looks like 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!
Different from the Stern-Brocot tree above, the rationals between 0 and 1 are paired (interleaved) with their reciprocal complements.
Try some Calkin-Wilf values yourself!
Bessel Functions
Studying this continued fraction (e2+1e2−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!
Gamma Functions
The factorial function is well known -
3!=3⋅2⋅1=6,
4!=4⋅3⋅2⋅1=12,
n!=n⋅(n−1)⋅(n−2)...
But what happens in between? The Gamma function, represented by the Greek capital, Γ(x)=(x−1)! includes all values, not just the integers, and has some interesting properties - especially when you consider the half values of Γ(x)√(π).
Chaos Theory and Cobweb Functions
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⋅x⋅(1−x)
But what happens next is far from simple!
Musical Continued Fractions
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!
And more...
Did You Know...? There is a connection between the Euclidean algorithm for finding the greatest common divisor of two numbers and continued fractions?
Tap the image to explore.
Interested to learn more about continued fractions?
Construct your own Model with GXWeb
Test Yourself
Share Your Results
Enter your name:
My class:
Email to:
Session report length: 0 characters.
Share with QR Code
GXWeb Jigsaws
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!
Behind the Scenes
©2021 Compass Learning Technologies ← GXWeb Showcase ← GXWeb Jigsaws and Quizzes ← GXWeb Fractured Fractions → GXWeb Fractured Fractions Collection