On continued fractions. Part 1: Introduction

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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:

$$$ r = a_0 + \frac{1}{a_1 + \frac{1}{a_2+\dots}} $$$

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:

$$$ \frac{1}{r-a_0} = [a_1, a_2, \dots, a_n] $$$

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

$$$ r_0 = \frac{a_0}{1},\\ r_1 = a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1},\\ r_2 = a_0 + \frac{a_2}{a_1 a_2 + 1} = \frac{a_0 a_1 a_2 + a_0 + a_2}{a_1 a_2 + 1}. $$$

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:

$$$ P_0(x_0) = x_0,\\ P_1(x_0, x_1) = x_0 x_1 + 1,\\ P_2(x_0, x_1, x_2) = x_0 x_1 x_2 + x_0 + x_2. $$$

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:

$$$ r_k = \frac{P_{k}(a_0, a_1, \dots, a_k)}{P_{k-1}(a_1, a_2, \dots, a_k)} $$$

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

$$$ r_k = a_0 + \frac{1}{s_{k-1}} = a_0 + \frac{P_{k-2}(a_2, a_3, \dots, a_k)}{P_{k-1}(a_1, a_2, \dots, a_k)} = \frac{a_0 P_{k-1}(a_1, a_2, \dots, a_k) + P_{k-2}(a_2, a_3, \dots, a_k)}{P_{k-1}(a_1, a_2, \dots, a_k)} $$$

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

$$$ P_k(a_0, a_1, \dots, a_k) = a_0 P_{k-1}(a_1, a_2, \dots, a_k) + P_{k-2}(a_2, a_3, \dots, a_k) $$$

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}$$$.

Formal proof

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

$$$ P_k(a_0, a_1, \dots, a_k) = a_k P_{k-1}(a_0, a_1, \dots, a_{k-1}) + P_{k-2}(a_0, a_1, \dots, a_{k-2}) $$$

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

$$$ \frac{p_{-1}}{q_{-1}} = \frac{1}{0}, \quad \frac{p_0}{q_0} = \frac{a_0}{1}, \quad \frac{p_k}{q_k} = \frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}} $$$

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:

$$$ P_k(x_0, x_1, \dots, x_k) = \det \begin{bmatrix} x_0 & 1 & 0 & \dots & 0 \\ -1 & x_1 & 1 & \dots & 0 \\ 0 & -1 & x_2 & \cdot & \vdots \\ \vdots & \vdots & \cdot & \ddots & 1 \\ 0 & 0 & \dots & -1 & x_k \end{bmatrix} $$$

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.

adamant's blog