The simple continued fraction expansion is an intriguing way of writing real numbers, which holds within it many interesting properties of the number itself. These continued fractions have a remarkable tendency to emerge in various places. For instance, you might have encountered the expansions for the golden ratio \(\varphi = \frac {1+\sqrt{5}}{2} \), \(\sqrt{2}\) or even \(e\) which look very interesting:
\( \varphi = 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\ddots}}}} \)
\( \sqrt{2} = 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\ddots}}}} \)
\( e = 2+\frac{1}{1+\frac{1}{2+\frac{1}{1+\frac{1}{1+\frac{1}{4+\frac{1}{1+\frac{1}{1+\cdots}}}}}}} \)
The origin of continued fractions
The origin of simple continued fractions traces back to Euclid’s greatest common divisor algorithm in 300 BCE. Starting with two integers \(n\geq m>0\), Euclid looked for their greatest common divisor \( gcd(n,m) \). His key insight was that if we divide \(n\) by \(m\), with quotient \(q\) and remainder \(0\leq r <m\), namely
\( n = m\cdot q + r\),
then \(gcd(n,m)\) is the same as \(gcd(m,r)\). This new pair \((m,r)\) is “simpler” than the original \((n,m)\) in the sense that the integers are smaller. Euclid then applied this division with remainder again and again to get a sequence, which must stop eventually at 0, namely
\(\gcd (n,m)=\gcd (m,r_1)=\gcd (r_1, r_2)=\cdots=\gcd (r_{n-1},r_n)=\gcd (r_n,0).\)
Finally, it is easily verified that \( gcd(r_n,0)=r_n\), thus providing an algorithm to compute the greatest common divisor of any two positive integers.
For example, let’s try to show that 49 and 36 are coprime, namely \( gcd(49, 36)=1 \). Running the algorithm we get:
\(\begin{array}{ccc}49 & =36\cdot1 & +13\\36 & =13\cdot2 & +10\\13 & =10\cdot1 & +3\\10 & =3\cdot3 & +1\\3 & =1\cdot3 & +0\end{array}\)
It follows that
\(gcd(49,36)=\gcd (36, 13)=\gcd (13, 10)=\gcd (10, 3)=\gcd (3, 1)=\gcd (1, 0)=1\).
But how do all of this relate to continued fractions? Well, we can use the algorithm above to write \(\frac{49}{36}\) and get:
\(\frac{49}{36} = \frac{36\cdot 1 + 13}{36} = 1 + \frac{13}{36} = 1 + \frac{1}{\frac{36}{13}} \).
Continuing in this fashion, we get that:
\(\frac{49}{36} = 1 + \frac{1}{\frac{36}{13}} = 1 + \frac{1}{2+\frac{1}{\frac{13}{10}}} = 1 + \frac{1}{2+\frac{1}{1+\frac{1}{ 3+ \frac{1}{3} }}}\).
In other words, the quotients we got along the way, namely \(1,2,1,3,3\), are exactly the coefficients that we see in (what eventually will be) the simple continued fraction.
The continued fraction expansion for real numbers
The process outlined above demonstrates the close connection between finding the greatest common divisor of \(n\) and \(m\) and obtaining the continued fraction expansion for \(\frac{n}{m}\). Interestingly enough, we can generalize it to any two positive numbers \(\alpha,\beta \in \mathbb{R}\). Namely, the “division” is done by looking for an integer quotient \(q\) and remainder \(0\leq r<\beta\), not necessarily an integer, such that
\( \alpha = \beta \cdot q + r\),
and the rest of the process is exactly like in Euclid’s algorithm.
Unlike with starting with two integers, generally this process does not terminate after finitely many steps, leading to infinite continued fraction expansions. More specifically, a continued fraction expansion corresponds to a rational number, if and only if the expansion is finite. Moreover, the process described above produces the (almost) unique expansion for \(\frac{\alpha}{\beta}\). Note, as the expansion is only a function of the ratio, we can (and will) assume that \(\beta = 1\).
The polynomial continued fraction
We can now use the process above to find the continued fraction for any number that we want, e.g. the golden ratio, \(\sqrt{2}\) or \(e\) from the beginning. However, in general the coefficients appearing in the expansion are not always as simple as in these three cases. For example, for \(\pi\) we have:
\(\pi=3+\frac{1}{7+ \frac{1}{15+ \frac{1}{1+ \frac{1}{292+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{2+ \ddots} } } } } } } }\),
there doesn’t seem to be a pattern in the coefficients \(3, 7, 15, 1, 292, 1, 1, 1, 2, … \) , making this expansion difficult to use or compute.
Since the expansion came from the “generalized” greatest common divisor algorithm, all the numerators in the expansion are 1. If we allow ourselves to have different numerators, while we would lose some of the number theoretic properties of the expansion that came with the algorithm (and we will go more into the details of this here), in return we might get “nicer” expansions. In particular, for \(\pi\) we have the following:
\(\pi + 3=6+\frac{1^2}{6+ \frac{3^2}{6+ \frac{5^2}{6+ \frac{7^2}{6+ \ddots + \frac{(2k-1)^2}{6+\ddots}} } } } \).
We call such expansions polynomial continued fractions as both the numerator and denominator can be described using polynomials (and in this case they are \((2k-1)^2\) and \(6\)).
This nicer presentation exist for many constants, and while it is “not as good” as the original continued fraction, it is much easier in general to work with, since we can easily find all the numerators and denominators in the expansion, and we don’t have to run Euclid’s algorithm step by step in order to find them. With this in mind, let us end with several other interesting polynomial continued fractions:
\(\frac{4}{\pi} =1+\frac{1^2} {3+ \frac{2^2} {5+ \frac{3^2} {7+ \ddots + \frac{k^2}{(2k+1)+\ddots} } } } \)
\(e =3-\frac{1} {4- \frac{2} {5- \frac{3} {6- \ddots + \frac{-k}{(k+3)+\ddots} } } } \)
\(\frac{1}{2G} =1-\frac{2} {7- \frac{32} {19- \frac{162} {37- \ddots + \frac{-2k^4}{((k+1)^3-k^3)+\ddots} } } } \)
where \(G=\sum_0^\infty \frac{(-1)^n}{(2n+1)^2}\) is the Catalan number.
\(\frac{4}{\pi} + 1=2+\frac{1^2}{2+ \frac{3^2}{2+ \frac{5^2}{2+ \ddots + \frac{(2k-1)^2}{2+\ddots} } } } \)
\(\frac{1}{e-1} =\frac{1} {1+ \frac{2} {2+ \frac{3} {3+ \ddots + \frac{k}{k+\ddots} } } } \)
\(\frac{1}{\zeta(d)} =1+\frac{-1^{2d}} {1^d+2^d+ \frac{-2^{2d}} {2^d+3^d+ \frac{-3^{2d}} {3^d+4^d+ \ddots + \frac{-k^{2d}}{(k^d+(k+1)^d)+\ddots} } } } \)
where \(\zeta(d) = \sum_0^\infty \frac{1}{k^d} \) is the Riemann zeta function (which converge for integers \( k\geq 2\)).