What is Lucas Numbers?

In this article, we will learn Lucas Numbers,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Lucas Numbers - ❤️Data Structures and Algorithms Tutorials In 2024

Lucas numbers are similar to Fibonacci numbers. Lucas numbers are also defined as the sum of its two immediately previous terms. But here the first two terms are 2 and 1 whereas in Fibonacci numbers the first two terms are 0 and 1 respectively.
Mathematically, Lucas Numbers may be defined as:
1.\\\end{cases}}} " title="Rendered by QuickLaTeX.com" height="111" width="365" style="vertical-align: -48px;">
The Lucas numbers are in the following integer sequence:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 …………..
Write a function int lucas(int n) n as an argument and returns the nth Lucas number.
Examples :

Input : 3
Output : 4

Input : 7
Output : 29

Method 1 (Recursive Solution)
Below is a recursive implementation based on a simple recursive formula.

C++

// Recursive C/C++ program  
// to find n'th Lucas number  
#include <stdio.h>  
  
// recursive function  
int lucas(int n)  
{  
    // Base cases  
    if (n == 0)  
        return 2;  
    if (n == 1)  
        return 1;  
  
    // recurrence relation  
    return lucas(n - 1) +  
        lucas(n - 2);  
}  
  
// Driver Code  
int main()  
{  
    int n = 9;  
    printf("%d", lucas(n));  
    return 0;  
}  

Java

// Recursive Java program to 
// find n'th Lucas number 
  
class GFG  
{ 
  
    // recursive function 
    public static int lucas(int n) 
    { 
  
        // Base cases 
        if (n == 0) 
            return 2; 
        if (n == 1) 
            return 1; 
  
        // recurrence relation 
        return lucas(n - 1) +  
               lucas(n - 2); 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        int n = 9; 
        System.out.println(lucas(n)); 
    } 
} 
// This code is contributed  
// by Nikita Tiwari. 

Python3

# Python3 program to 
# find n'th Lucas number 
  
# recursive function 
def lucas(n): 
    
    # Base cases 
    if n == 0: 
        return 2; 
    if n == 1: 
        return 1; 
    
    # recurrence relation 
    return lucas(n - 1) + lucas(n - 2); 
      
# Driver code to test above methods 
n = 9; 
print(lucas(n)); 
  
# This code is contributed by phasing17

C#

// Recursive C# program to 
// find n'th Lucas number 
using System; 
  
class GFG { 
  
    // recursive function 
    public static int lucas(int n) 
    { 
  
        // Base cases 
        if (n == 0) 
            return 2; 
        if (n == 1) 
            return 1; 
  
        // recurrence relation 
        return lucas(n - 1) + lucas(n - 2); 
    } 
  
    // Driver program 
    public static void Main() 
    { 
  
        int n = 9; 
  
        Console.WriteLine(lucas(n)); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php 
// Recursive php program to 
// find n'th Lucas number 
  
// recursive function 
function lucas($n) 
{ 
      
// Base cases  
if ($n == 0)  
    return 2; 
if ($n == 1)  
    return 1; 
  
// recurrence relation  
return lucas($n - 1) +  
       lucas($n - 2);  
} 
  
// Driver Code 
$n = 9; 
echo lucas($n); 
  
// This code is contributed by ajit. 
?> 

Javascript

<script> 
  
// Javascript program to 
// find n'th Lucas number 
  
    // recursive function 
    function lucas(n) 
    { 
    
        // Base cases 
        if (n == 0) 
            return 2; 
        if (n == 1) 
            return 1; 
    
        // recurrence relation 
        return lucas(n - 1) +  
               lucas(n - 2); 
    } 
  
// Driver code to test above methods 
  
        let n = 9; 
        document.write(lucas(n)); 
   
 // This code is contributed by avijitmondal1998. 
</script> 

Output :

Method 2 (Iterative Solution)
The time complexity of the above implementation is exponential. We can optimize it to work in O(n) time using iteration.

C++

// Iterative C/C++ program  
// to find n'th Lucas Number  
#include <stdio.h>  
  
// Iterative function  
int lucas(int n)  
{  
    // declaring base values  
    // for positions 0 and 1  
    int a = 2, b = 1, c, i;  
  
    if (n == 0)  
        return a;  
  
    // generating number  
    for (i = 2; i <= n; i++)  
    {  
        c = a + b;  
        a = b;  
        b = c;  
    }  
    return b;  
}  
  
// Driver Code  
int main()  
{  
    int n = 9;  
    printf("%d", lucas(n));  
    return 0;  
}  

Java

// Iterative Java program to 
// find n'th Lucas Number 
class GFG  
{ 
    // Iterative function 
    static int lucas(int n) 
    { 
        // declaring base values 
        // for positions 0 and 1 
        int a = 2, b = 1, c, i; 
  
        if (n == 0) 
            return a; 
  
        // generating number 
        for (i = 2; i <= n; i++)  
        { 
            c = a + b; 
            a = b; 
            b = c; 
        } 
        return b; 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        int n = 9; 
        System.out.println(lucas(n)); 
    } 
} 
  
// This code is contributed  
// by Nikita tiwari. 

Python3

# Iterative Python 3 program  
# to find n'th Lucas Number 
  
# Iterative function 
def lucas(n) : 
  
    # declaring base values 
    # for positions 0 and 1 
    a = 2
    b = 1
      
    if (n == 0) : 
        return a 
   
    # generating number 
    for i in range(2, n + 1) : 
        c = a + b 
        a = b 
        b = c 
      
    return b 
      
   
# Driver Code 
n = 9
print(lucas(n)) 
  
# This code is contributed 
# by Nikita tiwari. 

C#

// Iterative C# program to 
// find n'th Lucas Number 
using System; 
  
class GFG { 
  
    // Iterative function 
    static int lucas(int n) 
    { 
  
        // declaring base values 
        // for positions 0 and 1 
        int a = 2, b = 1, c, i; 
  
        if (n == 0) 
            return a; 
  
        // generating number 
        for (i = 2; i <= n; i++) { 
            c = a + b; 
            a = b; 
            b = c; 
        } 
  
        return b; 
    } 
  
    // Driver Code 
    public static void Main() 
    { 
        int n = 9; 
  
        Console.WriteLine(lucas(n)); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php 
// Iterative php program  
// to find n'th Lucas Number 
  
function lucas($n) 
{ 
    // declaring base values 
    // for positions 0 and 1 
    $a = 2; $b = 1; $c; $i; 
  
    if ($n == 0) 
        return $a; 
  
    // generating number 
    for ($i = 2; $i <= $n; $i++)  
    { 
        $c = $a + $b; 
        $a = $b; 
        $b = $c; 
    } 
    return $b; 
} 
  
// Driver Code 
$n = 9; 
echo lucas($n); 
  
// This code is contributed by ajit 
?> 

Javascript

<script> 
    // Iterative Javascript program to find n'th Lucas Number 
      
    // Iterative function 
    function lucas(n) 
    { 
   
        // declaring base values 
        // for positions 0 and 1 
        let a = 2, b = 1, c, i; 
   
        if (n == 0) 
            return a; 
   
        // generating number 
        for (i = 2; i <= n; i++) { 
            c = a + b; 
            a = b; 
            b = c; 
        } 
   
        return b; 
    } 
      
    let n = 9; 
   
      document.write(lucas(n)); 
          
</script>