# 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]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ir0nstone.gitbook.io/notes/cryptography/continued-fractions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.