# 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:

```python
f = continued_fraction(17/11)
```

We can then print off the list of coefficients:

```python
print(f)
>>> [1; 1, 1, 5]
```

And the convergents are even calculated for us:

```python
print(f.convergents())
>>> [1, 2, 3/2, 17/11]
```