Hi everyone!

After writing this article I've decided to write another one being comprehensive introduction into continued fractions for competitive programmers. I'm not really familiar with the topic, so I hope writing this entry will be sufficient way to familiarize myself with it :)

Part 1: Introduction
Part 2: Properties and interpretation

Definitions. To begin with, any rational number $$$r=\frac{p}{q}$$$ may be uniquely represented as a finite nested fraction of the following kind:

Where $$$a_0$$$ is integer number and $$$a_1, a_2, \dots, a_n$$$ are positive integer numbers and either $$$n=0$$$ or $$$a_n \neq 1$$$. It may be written shortly as $$$r = [a_0, a_1, \dots, a_n]$$$. Let's investigate it a bit. In the given constraints, $$$[a_1, a_2, \dots, a_n]$$$ is either absent or it is greater than $$$1$$$, which means that $$$r-a_0 < 1$$$. Given that $$$a_0$$$ is integer it allows us to conclude that $$$a_0 = \lfloor r \rfloor$$$. Next numbers in the sequence may be found from:

Since $$$a_0 = \lfloor \frac{p}{q}\rfloor$$$ we can write that $$$r-a_0 = \frac{p - \lfloor p/q\rfloor \cdot q}{q}=\frac{p \bmod q}{q}$$$, so if $$$\frac{p}{q} = [a_0, a_1, \dots, a_n]$$$ then $$$\frac{q}{p \bmod q} = [a_1, a_2, \dots, a_n]$$$. It provides us with important observation that if we have rational number defined by the pair $$$(p,q)$$$ we may recursively reduce the computation of its nested fraction coefficients to the case $$$(q, p \bmod q)$$$, which is the same transition we do in Euclidean algorithm.

Convergents. Let's analyze the sequence $$$r_0, r_1, \dots, r_n$$$ such that $$$r_k = [a_0, a_1, \dots, a_k] = \frac{p_k}{q_k}$$$. Its elements are called convergents. Let's look at some explicit formulas for initial convergents, given that we know $$$a_0, a_1, \dots$$$:

We may see some patterns, for example $$$r_k = a_0 + \frac{1}{s_{k-1}}$$$ where $$$s_{k-1}$$$ is the $$$(k-1)$$$-th convergent of $$$[a_1, \dots, a_n]$$$. Other important observation is that numerators and denominators of $$$r_k$$$ are polynomials of $$$a_0, \dots, a_k$$$. Let $$$P_k(x_0, \dots, x_k)$$$ be the polynomial corresponding to the numerator of $$$r_k$$$-th numerator, for example:

Since $$$r_k = a_0 + \frac{1}{s_{k-1}}$$$ we may conclude that denominator of $$$r_k$$$ is the numerator of $$$s_{k-1}$$$, therefore:

Substituting it into $$$r_k = a_0 + \frac{1}{s_{k-1}}$$$ we obtain the explicit recurrent formula:

Thus, the final formula for $$$P_k(a_0, a_1, \dots, a_k)$$$ is as follows:

To make this formula work for $$$k=0$$$ it's convenient to put $$$P_{-1}=1$$$ and $$$P_{-2}=0$$$, formally assuming $$$r_{-1}=\frac{1}{0}$$$. Though formula is not very convenient yet as we would rather like to use it to calculate numerators of $$$r_k$$$ knowing numerators for $$$r_{k-1}$$$, $$$r_{k-2}$$$ and so on. To do this we should notice that $$$P_k(a_0, a_1, \dots, a_k)=P_k(a_k, a_{k-1}, \dots, a_0)$$$. It may be proven by induction as it holds for $$$P_1$$$, $$$P_0$$$, $$$P_{-1}$$$ and $$$P_{-2}$$$.

Summary. Right now we obtained far more convenient formula for $$$P_k(a_0, a_1, \dots, a_k)$$$:

Which means that consequent convergents may be derived from one another using simple recurrent formula:

These formulas were derived by Leonhard Euler, numerator polynomial $$$P_k(x_0, x_1, \dots, x_k)$$$ is known as the continuant and has some other peculiar properties on its own. Most notably, it can be explicitly written as the determinant of tridiagonal matrix:

Which makes immediate explanation for why it's invariant under the reverse of arguments.

To be continued... I feel like article is long enough already and it has an outline of some key results to begin with, so I decided to cut it on this point. In further parts I'd like to write more about connection between continued fractions, Euclidean algorithms and number theory as well as their importance for Diophantine approximations, so stay tuned and thanks for reading!

P.S. If you were interested in the topic, you may read about one of its applications right away in this article about how one may recover rational number from its remainder modulo some huge number using continued fractions. There is also another article on Pell's equation by, LieutenantLolicon which heavily utilizes continued fractions. Also, it would be great if anyone may suggest some other competitive programming problems utilizing continued fractions to highlight them in future articles.