46.21 Lucas

`Lucas( P, Q, k )`

`Lucas` returns the k-th values of the Lucas sequence with parameters P and Q, which must be integers, as a list of three integers.

Let alpha, beta be the two roots of x^2 - P x + Q then we define
Lucas( P, Q, k )[1] = U_k = (alpha^k - beta^k) / (alpha - beta) and
Lucas( P, Q, k )[2] = V_k = (alpha^k + beta^k) and as a convenience
Lucas( P, Q, k )[3] = Q^k.

The following recurrence relations are easily derived from the definition
U_0 = 0, U_1 = 1, U_k = P U_{k-1} - Q U_{k-2} and
V_0 = 2, V_1 = P, V_k = P V_{k-1} - Q V_{k-2}.
Those relations are actually used to define `Lucas` if alpha = beta.

Also the more complex relations used in `Lucas` can be easily derived
U_{2k} = U_k V_k, U_{2k+1} = (P U_{2k} + V_{2k}) / 2 and
V_{2k} = V_k^2 - 2 Q^k, V_{2k+1} = ((P^2-4Q) U_{2k} + P V_{2k}) / 2.

`Fibonnaci(k)` (see Fibonacci) is simply `Lucas(1,-1,k)[1]`. In an abuse of notation, the sequence `Lucas(1,-1,k)[2]` is sometimes called the Lucas sequence.

```    gap> List( [0..10], i->Lucas(1,-2,i)[1] );
[ 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341 ]    # \$2^k - (-1)^k)/3\$
gap> List( [0..10], i->Lucas(1,-2,i)[2] );
[ 2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025 ]    # \$2^k + (-1)^k\$
gap> List( [0..10], i->Lucas(1,-1,i)[1] );
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]    # Fibonacci sequence
gap> List( [0..10], i->Lucas(2,1,i)[1] );
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]    # the roots are equal ```

GAP 3.4.4
April 1997