## Lucas Sequences

### October 1, 2013

We begin with a function that computes the first *n* elements of a Lucas sequence, given the first two elements of the sequence:

`(define (lucas l2 l1 n)`

(let loop ((n n) (l2 l2) (l1 l1) (ls (list l1 l2)))

(if (zero? n) (reverse ls)

(let ((l (+ l1 l2)))

(loop (- n 1) l1 l (cons l ls))))))

This can be used to calculate the Fibonacci and Lucas numbers:

`> (lucas 1 1 20) ; fibonacci numbers`

(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584

4181 6765 10946 17711)

> (lucas 1 3 20) ; lucas numbers

(1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571

5778 9349 15127 24476 39603)

Another approach uses *P*, *Q* and the first two elements of the sequence:

`(define (lucas p q l2 l1 n)`

(let loop ((n n) (l2 l2) (l1 l1) (ls (list l1 l2)))

(if (zero? n) (reverse ls)

(let ((l (- (* p l1) (* q l2))))

(loop (- n 1) l1 l (cons l ls))))))

And here are the Fibonacci and Lucas numbers again:

`> (lucas 1 -1 1 1 20)`

(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584

4181 6765 10946 17711)

> (lucas 1 -1 1 3 20)

(1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571

5778 9349 15127 24476 39603)

Our last functions are mutually-recursive functions that compute the *n*th element of a *U* or *V* sequence in time *O*(log *n*):

`(define (u n p q)`

(if (< n 1) 1 (if (= n 1) p

(let ((k (quotient n 2)))

(if (odd? n)

(- (* (u (+ k 1) p q) (v k p q)) (expt q k))

(* (u k p q) (v k p q)))))))

`(define (v n p q)`

(if (< n 1) 2 (if (= n 1) p

(let ((k (quotient n 2)))

(if (odd? n)

(- (* (v (+ k 1) p q) (v k p q)) (* p (expt q k)))

(- (expt (v k p q) 2) (* 2 (expt q k))))))))

Then we can compute particular elements of the Fibonacci or Lucas sequences:

`> (u 22 1 -1) ; fibonacci`

17711

> (v 22 1 -1) ; lucas

39603

You can run the program at http://programmingpraxis.codepad.org/90DQYRBD.

Here’s a Haskell version that gives two implementations: a linear update a la

the usual iterative Fibonacci procedure, and a (mutually) recursive one like

the last solution.

I’m away from my computer at the moment so I’m not sure if this works, but I like the following definition better (if it works):

[sourecode lang=”css”]

lucas x0 x1 p q = x0 : scanl (\x y -> p * x – q * y) x1 $ lucas x0 x1 p q

[/sourcecode]

Apologies for the phone keyboard typo.

In Python.

Oops, forgot the recursive formula for Lucas V.

[…] Lucas Sequences […]