How to find continued fraction of pi

I have always been amazed by the continued fractions for $\pi$. For example some continued fractions for pi are:

$\pi=[3:7,15,1,292,.....]$ and many others given here.

Similarly some nice continued fractions for $e$ and it's derivatives are given here.I have tried to prove that the are indeed the continued fractions but did not get very far.If any one can can help it would be great(especially if there is some easy way to get continued fraction of derivatives of e from the original continued fraction of e).Here derivatives of e I mean $\sqrt e,\frac{e-1}{e+1} $ etc.

Solution 1:

Here is how you find the continued fraction for any number at all. Say the number is $x_0$.

First, let $a_0$ be the largest integer that does not exceed $x_0$. That is, $a_0 = \lfloor x_0\rfloor$. And let $b_0$ be the fractional part of $x_0$, that is $b_0 = x_0 - a_0$. In our example, $$\begin{align}x_0&=\pi,\\ a_0 &= 3,\\ b_0 &= 0.14159\ldots.\end{align}$$

Now we write $$\begin{align}x_0 & = a_0 + b_0 \\ & = a_0 + \frac{1}{x_1}\end{align}$$ where $x_1 = \frac1{b_0}$. In this case we have $x_1 = \frac{1}{0.14159\ldots} = 7.0625\ldots$.

Then repeat: let $a_1 = \lfloor x_1\rfloor, b_1 = x_1-a_1,$ and $x_2 = \frac1{b_1}$. In this case we have $a_1 = 7, b_1 \approx 0.0625\ldots$, and $x_2 = 15.996\ldots$. At this point have $$\pi = 3 + \cfrac{1}{7+\cfrac{1}{15.996\ldots}},$$ and in general $$x_0 = a_0 + \cfrac{1}{a_1+\cfrac{1}{x_2}}$$

Repeat again: let $a_2 = \lfloor x_2\rfloor, b_2 = x_2-a_2,$ and $x_3 = \frac1{b_2}$. In this case we have $a_2 = 15, b_1 \approx 0.996\ldots$, and $x_3 = 1.003\ldots$.

Repeat as desired, or stop if $x_i$ becomes 0, which will happen if and only if the original $x_0$ was rational.

The $a_i$ are the terms of the continued fraction expansion.

For expressions like $$\frac{e-1}{e+1}$$ there is an algorithm you can use, due to Bill Gosper, which takes the continued fraction for $e$ as input and emits the terms of $\frac{e-1}{e+1}$ as output. The algorithm is too long to describe in detail here, but you can read it in Gosper's original monograph or a shorter explanation here. The algorithm will actually calculate $$\frac{ax+b}{cx+d}$$ for any integer $a,b,c,d$ and continued fraction $x$; for $\frac{e-1}{e+1}$ you need to take $a=c=d=1, b=-1,$ and $x=e$.

Note that this does not require a decimal approximation for $e$; all it requires is the continued fraction for $e$, which is simple: $[2; 1,2,1,1,4,1,1,6,1,1,8,1\ldots]$. The Gosper monograph also gives an algorithm for extracting a continued fraction for $\sqrt x$ when the continued fraction for $x$ is known.

You asked how to know, when calculating a continued fraction for $\pi$, how much precision you need in the input decimal. Suppose you have calculated that $\pi \approx [p_0; p_1, p_2, \ldots p_n]$. Then you know that $$[p_0; p_1, p_2, \ldots p_n]\lt \pi \lt [p_0; p_1, p_2,\ldots, p_{n-1}]$$ if $n$ is even, or with the inequalities reversed if $n$ is odd. Now the $[p_0; \ldots]$ parts are rational numbers, so you can look at the denominators and see if your approximation to $\pi$ was good enough to justify continued fractions of that precision.

You also asked how, if you don't already have a decimal expansion for $\pi$, you can calculate the continued fraction. The answer is, you calculate it the same way that you calculate the decimal expansion for $\pi$ in the first place: by using the terms of an infinite series. For example, you might use the well-known series $$\sum_{k=0}^\infty\frac{2^{k+1} k!^2}{(2k+1)!}=\pi.$$ Each term of this series is a single rational number. You can start with $x=0$ and use the Gosper algorithm to accumulate the terms into $x$, extracting a term of output when possible, because $x' = x+\frac pq = \frac{qx+p}{0x+q}$ which has the required form. Whenever the integer part of $x$ and $x'$ is the same, that is the next term of the continued fraction for $\pi$; otherwise, set $x←x', x'←x'+\frac pq$ where $\frac pq$ is the next rational number in the series, and continue. (Disclaimer: I have not actually tried this, but it might work.)

Solution 2:

Recently I have had some misgivings about using the other listed methods to compute continued fractions. It seems very inconvenient to be required to have a very good decimal approximation of your number before computing the convergents you want.

Here is a paper by Shiu which gives an algorithm for computing continued fractions without needing to know more decimal digits at each stage; it only requires your number ($\pi$ in your case) to be a zero of a sufficiently nice differentiable function. Here is the abstract:

An algorithm for the computation of the continued fraction expansions of numbers which are zeros of differentiable functions is given. The method is direct in the sense that it requires function evaluations at appropriate steps, rather than the value of the number as input in order to deliver the expansion. Statistical data on the first 10000 partial quotients for various real numbers are also given.

As for proving that a number has a specified continued fraction, that is much harder. For instance, there is no known pattern for the convergents of $\pi$ (and if you could find one, it would be pretty monumental). $e$ is special because its continued fraction follows a known pattern, which can be proved using so called Padé approximants. See one proof here.

Solution 3:

The digits in a continued fraction are given by

$$a_0 = x$$ $$a_n = (a_{n-1} - \lfloor a_{n - 1}\rfloor)^{-1}$$

$$d_n = \lfloor a_n \rfloor$$

Continued fraction for $\pi$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 3.1416 & 3 \\ \hline 1 & 0.1416^{-1} & = 7.0625 & 7 \\ \hline 2 & 0.0625^{-1} & = 15.9966 & 15 \\ \hline 3 & 0.9966^{-1} & = 1.0034 & 1 \\ \hline 4 & 0.0034^{-1} & = 292.6346 & 292 \\ \hline 5 & 0.6346^{-1} & = 1.5758 & 1 \\ \hline \end{array}$$

Continued fraction for $e$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 2.7183 & 2 \\ \hline 1 & 0.7183^{-1} & = 1.3922 & 1 \\ \hline 2 & 0.3922^{-1} & = 2.5496 & 2 \\ \hline 3 & 0.5496^{-1} & = 1.8194 & 1 \\ \hline 4 & 0.8194^{-1} & = 1.2205 & 1 \\ \hline 5 & 0.2205^{-1} & = 4.5356 & 4 \\ \hline \end{array}$$

Continued fraction for $\sqrt{e}$: $$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 1.6487 & 1 \\ \hline 1 & 0.6487^{-1} & = 1.5415 & 1 \\ \hline 2 & 0.5415^{-1} & = 1.8467 & 1 \\ \hline 3 & 0.8467^{-1} & = 1.1810 & 1 \\ \hline 4 & 0.1810^{-1} & = 5.5250 & 5 \\ \hline 5 & 0.5250^{-1} & = 1.9049 & 1 \\ \hline \end{array}$$

Continued fraction for $\frac {e - 1} {e + 1}$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 0.4621 & 0 \\ \hline 1 & 0.4621^{-1} & = 2.1640 & 2 \\ \hline 2 & 0.1640^{-1} & = 6.0993 & 6 \\ \hline 3 & 0.0993^{-1} & = 10.0711 & 10 \\ \hline 4 & 0.0711^{-1} & = 14.0554 & 14 \\ \hline 5 & 0.0554^{-1} & = 18.0454 & 18 \\ \hline \end{array}$$

It's more of a computation than a proof. Just make sure you have enough digits. When you start looking at the continued fractions that are patterns, then establishing the pattern actually requires proof techniques instead of just arithmetic.

Solution 4:

A neat method to construct a continued fraction for $\pi$ is to use the addition formula for $\arctan$: $$\arctan(x) + \arctan(y) = \arctan\left(\frac{x+y}{1-xy}\right)$$

which can also be written

$$\arctan\left(\frac{1}{x}\right) + \arctan\left(\frac{1}{y}\right) = -\arctan\left(\frac{x+y}{1-xy}\right) = \arctan\left(\frac{1}{x - \frac{1+x^2}{x+y}}\right)$$

Applying this formula one more time gives $$\arctan\left(\frac{1}{x}\right) + \arctan\left(\frac{1}{y}\right) + \arctan\left(\frac{1}{z}\right) = \arctan\frac{1}{z-\frac{1+z^2}{z + x - \frac{1+x^2}{x+y}}}$$

and by induction we arrive at

$$\arctan\left(\frac{1}{x_1}\right)-\arctan\left(\frac{1}{x_2}\right)+\arctan\left(\frac{1}{x_3}\right) - \ldots = \arctan\cfrac{1}{x_1+\cfrac{1+x_1^2}{x_2-x_1 + \cfrac{1+x_2^2}{x_3 - x_2 + \ddots}}}$$

If we now let $x_k = \frac{2k-1}{\epsilon}$ form an arithmetic series then

$$\sum_{k=1}^\infty (-1)^{k-1}\arctan\left(\frac{\epsilon}{2k-1}\right) = \arctan\cfrac{\epsilon}{1+\cfrac{1+\epsilon^2}{2 + \cfrac{9+\epsilon^2}{2 + \cfrac{25+\epsilon^2}{2 + \ddots}}}}$$

Dividing by $\epsilon$ and taking $\epsilon\to 0$ gives us

$$1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \ldots = \cfrac{1}{1+\cfrac{1}{2 + \cfrac{9}{2 + \cfrac{25}{2 + \ddots}}}} = \frac{\pi}{4}$$

since the series on the left is just Leibniz formula for $\frac{\pi}{4}$. This can be used to generate other simple continued fractions with known sum by taking $x_k = \frac{ak+b}{\epsilon}$ (as long as we are able to evaluate $\sum(-1)^{k-1}\frac{1}{ak+b}$). The value of this particular continued fraction was first found by Brouncker and I came across it, and the method used to generate it, in an article by Viggo Brun in an old mathematics journal from the 1950's (it was not specified what method Brouncker used to derive it, other than that he derived it after learning about Wallis product formula).