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 

Previous Up Top Next
Index