*by*Simon Plouffe

CECM

- The basic algorithm starts with a number x=x(0 ) and successively
calculates the y(n) by using this formula.

This will yield a sequence [y(0),y(1),y(2),...,y(k)] called the convergents of the continued fraction expansion of x. Usually n digits of x will yield approximately n convergents [**Knuth**]. In order to detect any pattern we need enough digits, which in turn will yield enough convergents. A good test starts with 16 digits, just enough for GFUN to detect a generating function.

Example : with x = tan(1) = 1.557407724654902... we obtain:

`
`` `1.557407724654902 =
` 1
1 + -------------------------------------------
1
1 + ---------------------------------------
1
1 + -----------------------------------
1
3 + -------------------------------
1
1 + ---------------------------
1
5 + -----------------------
1
1 + -------------------
1
7 + ---------------
1
1 + -----------
1
9 + -------
1 + ...
`

Which gives us the sequence of convergents : [1, 1, 1, 3, 1, 5, 1, 7, 1,9, 1, 11, 1, 13, 1]. We are now in a position to ask GFUN to try to guess a generating function. GFUN is part of the Share Library of Maple. Clicking on that sequence will launch a request to the Sequence Server at AT&T Research Labs.

sample MapleV session , ... (we now take the sequence),...

[1, 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 1] ;

> with(share);readshare(gfun,calculus);guessgf(",x):factor("); 2 3 1 + x - x + x [-----------------, ogf] 2 2 (x - 1) (x + 1)

- Computing the generating
function of a series given its first few terms, by François Bergeron
and Simon Plouffe, Experimental Mathematics, Vol. 1 #4, 1992.

An Introduction to the Theory of Numbers, by G.H. Hardy and E.M. Wright, Oxford Univ. Press.

Hanbook of mathematical functions ,by M. Abramowitz and Irene Stegun, Dover 1964.

The Art of Computing Programming by Donald E. Knuth, vol. 2 ,

isc@cecm.sfu.ca