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
. We can form a sequence of positive integers from
α1\alpha_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
​For example, let's say
α1=1.5\alpha_1=1.5
​. We can say that
α1=1+12,with α2=2\alpha_1 = 1 + \frac{1}{2}, \text{with } \alpha_2 = 2
​The trick here is that if
α2∉Z\alpha_2\not\in \mathbb{Z}
, we can continue this exact process with
α2\alpha_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}}}

Example

Let's take another example, that of
1711\frac{17}{11}
:
​
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}}}
​The list of continued fractions is represented as a list of the coefficients
aia_i
, in this case
1711=[1;1,1,5]\frac{17}{11} = \left[ 1; 1, 1, 5 \right]

Convergents

The
kk
th convergent of a continued fraction is the approximation of the fraction we gain by truncating the continued fraction and using only the first
kk
terms of the sequence, for example the 2nd convergence of
1711\frac{17}{11}
is
1+11=21=21 + \frac{1}{1} = \frac{2}{1} = 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}
.
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
      , the real number you are attempting to approximate
  • They are alternately greater than and less than
    α1\alpha_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]