Finding the regular continued fraction of a rational multiple m/n of e1/q

The algorithm is described in the paper Some properties of the continued fraction expansion of (m/n)e1/q, K.R. Matthews and R.F.C. Walters, Proc. Camb. Phil. Soc. (1970), 67, 67-74. It uses a version of Satz 4.1. of Die Lehre von den Kettenbrüchen, Band 1, S. 111. Inside the program, m and n are replaced by m'=m/gcd(m,n) and n'=n/gcd(m,n).

We limit input to m'n' ≤ 2000.
The paper shows that there is a quasi-period consisting of d=mn linear expressions of the form pt22qx+qt, t=1,...,d. A criteria is given for all the pt to be equal to 1. In the first version of this program, a zero partial quotient was present, being located at the end of the factorizations of the first or the start of the factorization of the second matrix in Theorem 1 (b) of the paper. This is now removed, thanks to an elegant proof of Alan Offer on 30th June 2010. We also have improved the code for getting the "initial" matrix, by using a suggestion of Alan that we use the recurrence relations of his proof.

Enter m (> 0):
Enter n (> 0):
Enter q (≥ 1):

Last modified 4th July 2010
Return to main page