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.

About these ads

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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: