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 $\alpha_1$. We can form a sequence of positive integers from $\alpha_1$ in this way:

$$\alpha_1 = a_1 + \frac{1}{\alpha_2}, \text{where } a_1=\left \lfloor{x}\right \rfloor$$

​For example, let's say $\alpha_1=1.5$​. We can say that

$$\alpha_1 = 1 + \frac{1}{2}, \text{with } \alpha_2 = 2$$

​The trick here is that if $\alpha_2\not\in \mathbb{Z}$, we can continue this exact process with $\alpha_2$ and keep the continued fraction going.

$$\alpha_1 = a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots}}}$$

Example

Let's take another example, that of $\frac{17}{11}$:

$$\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 $a_i$, in this case

$$\frac{17}{11} = \left[ 1; 1, 1, 5 \right]$$

Convergents

The $k$th convergent of a continued fraction is the approximation of the fraction we gain by truncating the continued fraction and using only the first $k$ terms of the sequence, for example the 2nd convergence of $\frac{17}{11}$ is $1 + \frac{1}{1} = \frac{2}{1} = 2$​ while the 3rd would be $1 + \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 $\alpha_1$, the real number you are attempting to approximate

• They are alternately greater than and less than $\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]