Lucas Numbers
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 :
76
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> |
Output :
76
Time complexity: O(n) since using a for loop
Space complexity: O(1) since using constant variables, since no extra space has been taken.
References:
https://en.wikipedia.org/wiki/Lucas_number
Contact Us