## Continued Fractions and Characteristic Recurrences

```It's easy to find the best fractional approximations for the square
root of 2, based on the simple continued fraction.  This gives
convergents 7/5, 17/12, 41/29, and so on.  However, it's not so
easy to define the analagous sequence for CUBE root of 2.

Lagrange proved the simple continued fraction of an irrational
number is periodic if and only if the number is a quadratic
irrational, i.e., the root of a quadratic equation, such as
x^2 - 2 = 0.  As a result, the numerators and denominators of
successive convergents of the continued fraction for sqrt(N) can
always be generated by a simple second order linear recurrence.
This corresponds to the solutions of the basic "Pell equation"
x^2 - Ny^2 = 1.  On the other hand, solutions of the analagous
equation x^3 - Ny^3 = 1 for cubes are less well-behaved.

Nevertheless, it's always possible to construct a linear recurring
sequence of integers s[0], s[1], s[2],... such that any specified
algebraic number is approached by some function of the ratio of
successive terms s[n+1]/s[n].  In particular, to construct a
sequence for the rth root of N, let m denote the largest integer
such that m^r < N.  Then we have the rth order recurrence relation

r   / r \   (r-j)       (j-1)
s[n]  =  SUM  (     ) m     (N-m^r)     s[n-j]
j=1  \ j /

with the initial values s[0]=s[1]=..s[r-2]=0 and s[r-1]=1,
any by construction we have

s[n]
N^(1/r)  =   lim     m + (N-m^r) ------
n->inf               s[n+1]

For example, to construct the sequence for the cube root of 2
we have N=2 and r=3, so m=1 and the recurrence is

s[n] = 3 s[n-1] + 3 s[n-2] + s[n-3]

The approximations for 2^(1/3) given by successive ratios of
terms in this sequence are listed below, along side the convergents
of the continued fraction

generated by            convergents of
linear recurrence       continued fraction  1/|N(N-DV)|

4/3 *                 4/3       1.135
5/4 *                 5/4       5.040
29/23 *               29/23       1.581
223/177                 34/27       1.646
63/50       4.021
286/227 *             286/227       1.682
3301/2620               349/277       1.533
635/504 *             635/504       7.530
5429/4309 *           5429/4309       0.940
6064/4813 *           6064/4813      12.546
723235/574032           90325/71691       0.924
463753/368081           96389/76504       8.964
10705243/8496757        1054215/836731       2.298
957826/760227       2204819/1749966       1.368
52819267/41922680       3259034/2586697       3.787
15240955/12096754 *   15240955/12096754       8.806
2345474521/186104361   186150494/147747745       1.834

Those marked with an asterisk are the same on both lists.  This
raises the interesting question of whether infinitely many
convergents occur in the sequence generated by the 3rd order
recurrence.

We might also wonder which of the above approximations is the
"best".  Obviously the absolute accuracy improves indefinitely,
but we can define a notion of "goodness" by considering the
ratio of how many digits of accuracy are achieved per digit
of the numerator and denominator.  One such measure for the
approximation N/D to the value V is 1/|N(N-DV)|.  The goodness
of each convergent is listed in the right hand column of the
table above.

It's interesting that the goodness of the continued fractions
never falls much below 1.0, whereas the linear recurrence
approximations can have very low values of "goodness".  For
example, the goodness of 723235/574032 is just 0.0122.

I wonder what can be said about the distribution of "goodness" of
continued fraction convergents.  For example, how soon would we
expect a convergent with more goodness than 12.546, which is the
maximum for all the values listed in the table?
```