Print nth iteration of Lucas Sequence in Python

We all know about the Fibonacci sequence. It is a sequence where any term is the sum of the previous two terms. The Lucas sequence is the same but with different starting values. While a Fibonacci sequence begins with 0 and 1, a Lucas sequence begins with 2 and 1 respectively. The other successive terms of Lucas sequence are 3, 4, 7, 11 ….and so on.

Printing nth iteration of Lucas Sequence in Python

In this tutorial, we are going to write a Python code that would take a number n as input and print nth iteration of the Lucas sequence. Let’s see how we can do this.

Approach 1:

This is a simple method. In this method, we create a recursive function as shown below to calculate the nth term adding the previous two terms. The first two terms are initialized as 2 and 1 as you can see in the program. See the code for better understanding.

def lucas(n):
    if n==0:
        return 2
    if n==1:
        return 1
    return lucas(n-1) + lucas(n-2)

print(lucas(5))

Output:

11

Approach 2:

This method performs better than the previous one. In the above method, we are calculating the same values again and again. This results in slower performance. We can improve our code by storing only the last two values- the current term and the previous term. See the below code.

def lucas(n):
    prev, curr = 2, 1
    for _ in range(n):
        prev, curr = curr, prev+curr
    return prev

print(lucas(5))

Output:

11

Approach 3:

This method uses the golden ratio. Two numbers are said to be in golden ratio if the ratio of their sum and the larger number is equal to the ratio of the larger number and the smaller number. We can use this ratio to find any number in Lucas Sequence. See the code below.

GoldenRatio = (1 + 5**0.5)/2

def Lucas(n):
    if n==0:
        return 2
    if n==1:
        return 1
    return round(GoldenRatio ** n)
    
print(Lucas(5))

 

Output:

11

Note: This method is faster than the above two but does not work properly for higher values of n and starts showing the wrong output.

Thank you.

Also, read: How to print Lucas series in C++

Leave a Reply

Your email address will not be published. Required fields are marked *