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 x2 − P x + Q = 0 are a = (P + sqrt(D)) / 2 and b = (P − sqrt(D)) / 2. Then Un(p, q) = (an − an) / (a − b) 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 Vn − Qn, V2n = Vn2 − 2 Qn, and V2n+1 = Vn+1 Vn − P 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

Posted by programmingpraxis
Filed in Exercises
6 Comments »

6 Responses to “Lucas Sequences”

  1. Graham said
    October 2, 2013 at 1:26 PM

    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
    October 2, 2013 at 5:00 PM

    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
    October 2, 2013 at 5:00 PM

    Apologies for the phone keyboard typo.

  4. Paul said
    October 4, 2013 at 6:56 AM

    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
    October 4, 2013 at 6:58 AM

    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

Leave a comment