## Lucas Sequences

### October 1, 2013

We studied Fibonacci numbers in a previous exercise. In today’s exercise, we will look at a generalization of Fibonacci numbers called Lucas numbers, which were studied by Edouard Lucas in the late 1800s.

Recall that each Fibonacci number is the sum of the two previous Fibonacci numbers, with the first two being 1 and 1; thus, the Fibonacci numbers begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. The definition of the Lucas numbers is similar, but the first two Lucas numbers are 1 and 3; thus, the Lucas numbers begin 1, 3, 4, 7, 11, 18, 29, 47, 76, …, and they grow faster than the Fibonacci numbers.

Lucas went on to generalize the Fibonacci numbers even further. He define two sequences Un(P, Q) and Vn(P, Q) as follows: Start with integer P and Q satisfying D = P2 − 4Q > 0. Then, by the quadratic formula, the roots of x2P x + Q = 0 are a = (P + sqrt(D)) / 2 and b = (P − sqrt(D)) / 2. Then Un(p, q) = (anan) / (ab) and Vn(P, Q) = an + an.

Now the Fibonacci and Lucas numbers are just special cases of the U and V sequences: the Fibonacci numbers are Un(1, -1) and the Lucas numbers are Vn(1, -1).

It is easy to compute a particularU or V sequence. The formulas are similar to the method of computing the Fibonacci sequence: Um(P,Q) = P Um−1(P,Q) − Q Um−2(P,Q) and Vm(P,Q) = P Vm−1(P,Q) − Q Vm−2(P,Q).

It is also easy to calculate a particular U or V in the sequence using a chain that takes only logarithmic time based on the following identities: U2n = Un Un, U2n+1 = Un+1 VnQn, V2n = Vn2 − 2 Qn, and V2n+1 = Vn+1 VnP Qn.

You can see all of these formulas at MathWorld. Our interest in Lucas sequences isn’t merely academic; we’ll see an application of Lucas sequences in a future exercise.

Your task is to write programs that compute the U and V sequences and that compute any given element of either of the two sequences. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Lucas Sequences”

1. Graham said

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.

```import Control.Arrow ((&&&))

lucas :: Integer -> Integer -> Integer -> Integer -> [Integer]
lucas x0 x1 p q = x0 : x1 : zipWith (\x y-> p * x - q * y) as bs
where
as = lucas x0 x1 p q
bs = tail as

u1 :: Integer -> Integer -> [Integer]
u1 = lucas 0 1

v1 :: Integer -> Integer -> [Integer]
v1 p = lucas 2 p p

u2 :: Integer -> Integer -> Integer -> Integer
u2 p q n | n <= 0    = 0
| n == 1    = 1
| odd n     = u2 p q (k + 1) * v2 p q k - q^k
| otherwise = u2 p q k * v2 p q k
where
k = n `div` 2

v2 :: Integer -> Integer -> Integer -> Integer
v2 p q n | n <= 0    = 2
| n == 1    = p
| odd n     = v2 p q (k + 1) * v2 p q k - p * q^k
| otherwise = v2 p q k ^2  - 2 * q^k
where
k = n `div` 2

main :: IO ()
main = do
let (p,q) = (1,-1)
mapM_ (print . take 17) [u1 p q, v1 p q]
print \$ map (u2 p q &&& v2 p q) [0..16]
```
2. Graham said

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]

3. Graham said

Apologies for the phone keyboard typo.

4. Paul said

In Python.

```# see http://mathworld.wolfram.com/LucasSequence.html
def U(P, Q):
"""generates Lucas U series - the first item is U1"""
if P ** 2 - 4 * Q <= 0:
raise ValueError("D is not positive")
a, b = 0, 1
while 1:
yield b
a, b = b, P * b - Q * a

def V(P, Q):
"""generates Lucas V series - the first item is V1"""
if P ** 2 - 4 * Q <= 0:
raise ValueError("D is not positive")
a, b = 2, P
while 1:
yield b
a, b = b, P * b - Q * a

def Un(P, Q, n):
"""recursive formula for Lucas U"""
if n in (0,1):
return n
m = n // 2
if n & 1:
return Un(P, Q, m+1) * Vn(P, Q, m) - Q ** m
else:
return Un(P, Q, m) * Vn(P, Q, m)
```
5. Paul said

Oops, forgot the recursive formula for Lucas V.

```# see mathworld.wolfram.com/LucasSequence.html
def U(P, Q):
"""generates Lucas U series - the first item is U1"""
if P ** 2 - 4 * Q <= 0:
raise ValueError("D is not positive")
a, b = 0, 1
while 1:
yield b
a, b = b, P * b - Q * a

def V(P, Q):
"""generates Lucas V series - the first item is V1"""
if P ** 2 - 4 * Q <= 0:
raise ValueError("D is not positive")
a, b = 2, P
while 1:
yield b
a, b = b, P * b - Q * a

def Un(P, Q, n):
"""recursive formula for Lucas U"""
if n in (0,1):
return n
m = n // 2
if n & 1:
return Un(P, Q, m+1) * Vn(P, Q, m) - Q ** m
else:
return Un(P, Q, m) * Vn(P, Q, m)

def Vn(P, Q, n):
"""recursive formula for Lucas V"""
if n in (0,1):
return (2, P)[n]
m = n // 2
if n & 1:
return Vn(P, Q, m+1) * Vn(P, Q, m) - P * Q ** m
else:
return Vn(P, Q, m) ** 2 - 2 * Q ** m
```
6. […] Lucas Sequences […]