Continued Fractions

Overview
Continued Fractions are a way of representing real numbers as a sequence of positive integers. Let's say we have a real number α1\alpha_1α1​
. We can form a sequence of positive integers from α1\alpha_1α1​
 in this way:
α1=a1+1α2,where a1=⌊x⌋\alpha_1 = a_1 + \frac{1}{\alpha_2}, \text{where } a_1=\left \lfloor{x}\right \rfloor α1​=a1​+α2​1​,where a1​=⌊x⌋
​For example, let's say α1=1.5\alpha_1=1.5α1​=1.5
​. We can say that
α1=1+12,with α2=2\alpha_1 = 1 + \frac{1}{2}, \text{with } \alpha_2 = 2α1​=1+21​,with α2​=2
​The trick here is that if α2∉Z\alpha_2\not\in \mathbb{Z}α2​∈Z
, we can continue this exact process with α2\alpha_2α2​
 and keep the continued fraction going.
α1=a1+1a2+1a3+1⋱\alpha_1 = a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots}}}α1​=a1​+a2​+a3​+⋱1​1​1​
Example
Let's take another example, that of 1711\frac{17}{11}1117​
:
​
1711=1+611=1+1116=1+11+56=1+11+165=1+11+11+15\frac{17}{11} = 1 + \frac{6}{11} = 1 + \frac{1}{\frac{11}{6}} = 1 + \frac{1}{1 + \frac{5}{6}}  = 1 + \frac{1}{1 + \frac{1}{\frac{6}{5}}} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{5}}}1117​=1+116​=1+611​1​=1+1+65​1​=1+1+56​1​1​=1+1+1+51​1​1​
​The list of continued fractions is represented as a list of the coefficients aia_iai​
, in this case
1711=[1;1,1,5]\frac{17}{11} = \left[ 1; 1, 1, 5 \right]1117​=[1;1,1,5]
Convergents
The kkk
th convergent of a continued fraction is the approximation of the fraction we gain by truncating the continued fraction and using only the first kkk
 terms of the sequence, for example the 2nd convergence of 1711\frac{17}{11}1117​
 is 1+11=21=21 + \frac{1}{1} = \frac{2}{1} = 21+11​=12​=2
​ while the 3rd would be 1+11+11=1+12=321 + \frac{1}{1 + \frac{1}{1}} = 1 + \frac{1}{2} = \frac{3}{2}1+1+11​1​=1+21​=23​
.
One of the obvious applications of these convergents is as rational approximations to irrational numbers.
Properties of Convergences
As a sequence, they have a limit
This limit is α1\alpha_1α1​
, the real number you are attempting to approximate
They are alternately greater than and less than α1\alpha_1α1​
​
Sage
In Sage, we can define a continue fraction very easily:
f = continued_fraction(17/11)
We can then print off the list of coefficients:
print(f)
>>> [1; 1, 1, 5]
And the convergents are even calculated for us:
print(f.convergents())
>>> [1, 2, 3/2, 17/11]
Last modified 1yr ago