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 kkth 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]

Last updated