Jacobsthal numbers
The Jacobsthal numbers are the numbers obtained by the Uns in the Lucas sequence with P=1 and Q=-2, corresponding to a = 2 and b = -1.
Jacobsthal numbers are defined by the recurrence relation:
The first Jacobsthal numbers are:
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, ……
Jacobsthal-Lucas numbers
Jacobsthal-Lucas numbers represent the complementary Lucas sequence Vn(1, -2). They satisfy the same recurrence relation as Jacobsthal numbers but have different initial values:
Given a positive integer n, the task is to find nth Jacobsthal and Jacobsthal-Lucas numbers.
Examples :
Input : n = 5
Output :
Jacobsthal number: 11
Jacobsthal-Lucas number: 31Input : n = 4
Output :
Jacobsthal number: 5
Jacobsthal-Lucas number: 17
Below is the implementation of finding nth Jacobsthal and Jacobsthal-Lucas numbers using recursion.
C++
// A simple C++ recursive solution to find// Jacobsthal and Jacobsthal-Lucas numbers#include <bits/stdc++.h>using namespace std;// Return nth Jacobsthal number.int Jacobsthal(int n){ // base case if (n == 0) return 0; // base case if (n == 1) return 1; // recursive step. return Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2);}// Return nth Jacobsthal-Lucas number.int Jacobsthal_Lucas(int n){ // base case if (n == 0) return 2; // base case if (n == 1) return 1; // recursive step. return Jacobsthal_Lucas(n - 1) + 2 * Jacobsthal_Lucas(n - 2);}// Driven Programint main(){ int n = 5; cout << "Jacobsthal number: " << Jacobsthal(n) << endl; cout << "Jacobsthal-Lucas number: " << Jacobsthal_Lucas(n) << endl; return 0;} |
Java
// A simple recursive solution// to find Jacobsthal and// Jacobsthal-Lucas numbersimport java.lang.*;import java.util.*;public class GfG { // Return nth Jacobsthal number. public static int Jacobsthal(int n) { // base case if (n == 0) return 0; // base case if (n == 1) return 1; // recursive step. return Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2); } // Return nth Jacobsthal-Lucas number. public static int Jacobsthal_Lucas(int n) { // base case if (n == 0) return 2; // base case if (n == 1) return 1; // recursive step. return Jacobsthal_Lucas(n - 1) + 2 * Jacobsthal_Lucas(n - 2); } // Driver function public static void main(String argc[]) { int n = 5; System.out.println("Jacobsthal number: " + Jacobsthal(n)); System.out.println("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n)); }}/* This code is contributed Sagar Shukla */ |
Python3
# A simple Python3 recursive solution to# find Jacobsthal and Jacobsthal-Lucas# numbers# Return nth Jacobsthal number.def Jacobsthal(n): # base case if (n == 0): return 0 # base case if (n == 1): return 1 # recursive step. return Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2)# Return nth Jacobsthal-Lucas number.def Jacobsthal_Lucas(n): # base case if (n == 0): return 2 # base case if (n == 1): return 1 # recursive step. return Jacobsthal_Lucas(n - 1) + 2 * Jacobsthal_Lucas(n - 2)# Driven Programn = 5print("Jacobsthal number:", Jacobsthal(n))print("Jacobsthal-Lucas number:", Jacobsthal_Lucas(n))# This code is contributed by Smitha Dinesh Semwal |
C#
// A simple recursive solution// to find Jacobsthal and// Jacobsthal-Lucas numbersusing System;public class GfG { // Return nth Jacobsthal number. public static int Jacobsthal(int n) { // base case if (n == 0) return 0; // base case if (n == 1) return 1; // recursive step. return Jacobsthal(n - 1) + 2 * Jacobsthal(n - 2); } // Return nth Jacobsthal-Lucas number. public static int Jacobsthal_Lucas(int n) { // base case if (n == 0) return 2; // base case if (n == 1) return 1; // recursive step return Jacobsthal_Lucas(n - 1) + 2 * Jacobsthal_Lucas(n - 2); } // Driver function public static void Main() { int n = 5; Console.WriteLine("Jacobsthal number: " + Jacobsthal(n)); Console.WriteLine("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n)); }}// This code is contributed vt_m |
PHP
<?php// A simple PHP recursive solution // to find Jacobsthal and // Jacobsthal-Lucas numbers // Return nth Jacobsthal number.function Jacobsthal($n){ // base case if ($n == 0) return 0; // base case if ($n == 1) return 1; // recursive step. return Jacobsthal($n - 1) + 2 * Jacobsthal($n - 2);}// Return nth Jacobsthal-// Lucas number.function Jacobsthal_Lucas($n){ // base case if ($n == 0) return 2; // base case if ($n == 1) return 1; // recursive step. return Jacobsthal_Lucas($n - 1) + 2 * Jacobsthal_Lucas($n - 2);}// Driven Code$n = 5;echo "Jacobsthal number: " , Jacobsthal($n) , "\n";echo "Jacobsthal-Lucas number: ", Jacobsthal_Lucas($n), "\n";// This code is contributed by aj_36 ?> |
Javascript
<script>// JavaScript program to find max xor sum// of 1 to n using atmost k numbers // Return nth Jacobsthal number. function Jacobsthal(n) { let dp = []; // base case dp[0] = 0; dp[1] = 1; for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Return nth Jacobsthal-Lucas number. function Jacobsthal_Lucas(n) { let dp = []; // base case dp[0] = 2; dp[1] = 1; for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Driver code let n = 5; document.write("Jacobsthal number: " + Jacobsthal(n) + "<br/>"); document.write("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n));</script> |
Output
Jacobsthal number: 11 Jacobsthal-Lucas number: 31
Time Complexity: O(2^n), Where n is the given number
Auxiliary Space: O(1)
Below is the implementation of finding nth Jacobsthal and Jacobsthal-Lucas numbers using Dynamic Programming.
C++
// A DP based solution to find Jacobsthal// and Jacobsthal-Lucas numbers#include <bits/stdc++.h>using namespace std;// Return nth Jacobsthal number.int Jacobsthal(int n){ int dp[n + 1]; // base case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n];}// Return nth Jacobsthal-Lucas number.int Jacobsthal_Lucas(int n){ int dp[n + 1]; // base case dp[0] = 2; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n];}// Driven Programint main(){ int n = 5; cout << "Jacobsthal number: " << Jacobsthal(n) << endl; cout << "Jacobsthal-Lucas number: " << Jacobsthal_Lucas(n) << endl; return 0;} |
Java
// A DP based solution// to find Jacobsthal and// Jacobsthal-Lucas numbersimport java.lang.*;import java.util.*;public class GfG { // Return nth Jacobsthal number. public static int Jacobsthal(int n) { int[] dp = new int[n + 1]; // base case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Return nth Jacobsthal-Lucas number. public static int Jacobsthal_Lucas(int n) { int[] dp = new int[n + 1]; // base case dp[0] = 2; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Driver function public static void main(String argc[]) { int n = 5; System.out.println("Jacobsthal number: " + Jacobsthal(n)); System.out.println("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n)); }}/* This code is contributed Sagar Shukla */ |
Python3
# A DP based solution to find# Jacobsthal and Jacobsthal-# Lucas numbers# Return nth Jacobsthal number.def Jacobsthal(n): dp = [0] * (n + 1) # base case dp[0] = 0 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i - 1] + 2 * dp[i - 2] return dp[n]# Return nth Jacobsthal-# Lucas number.def Jacobsthal_Lucas(n): dp = [0] * (n + 1) # base case dp[0] = 2 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i - 1] + 2 * dp[i - 2] return dp[n]# Driven Programn = 5print("Jacobsthal number:", Jacobsthal(n))print("Jacobsthal-Lucas number:", Jacobsthal_Lucas(n))# This code is contributed by Smitha Dinesh Semwal |
C#
// A DP based solution// to find Jacobsthal and// Jacobsthal-Lucas numbersusing System;public class GfG { // Return nth Jacobsthal number. public static int Jacobsthal(int n) { int[] dp = new int[n + 1]; // base case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Return nth Jacobsthal-Lucas number. public static int Jacobsthal_Lucas(int n) { int[] dp = new int[n + 1]; // base case dp[0] = 2; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n]; } // Driver Code public static void Main() { int n = 5; Console.WriteLine("Jacobsthal number: " + Jacobsthal(n)); Console.WriteLine("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n)); }}// This code is contributed vt_m |
PHP
<?php// A DP based solution to // find Jacobsthal and // Jacobsthal-Lucas numbers // Return nth Jacobsthal number.function Jacobsthal($n){ //$dp[$n + 1]; // base case $dp[0] = 0; $dp[1] = 1; for ($i = 2; $i <= $n; $i++) $dp[$i] = $dp[$i - 1] + 2 * $dp[$i - 2]; return $dp[$n];}// Return nth Jacobsthal-// Lucas number.function Jacobsthal_Lucas($n){ // $dp[$n + 1]; // base case $dp[0] = 2; $dp[1] = 1; for ($i = 2; $i <= $n; $i++) $dp[$i] = $dp[$i - 1] + 2 * $dp[$i - 2]; return $dp[$n];}// Driver Code$n = 5;echo "Jacobsthal number: " , Jacobsthal($n), "\n";echo "Jacobsthal-Lucas number: " , Jacobsthal_Lucas($n), "\n"; // This code is contributed by ajit?> |
Javascript
<script>// A DP based solution// to find Jacobsthal and// Jacobsthal-Lucas numbers// Return nth Jacobsthal number.function Jacobsthal(n){ let dp = new Array(n + 1); // Base case dp[0] = 0; dp[1] = 1; for(let i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n];}// Return nth Jacobsthal-Lucas number.function Jacobsthal_Lucas(n){ let dp = new Array(n + 1); // Base case dp[0] = 2; dp[1] = 1; for(let i = 2; i <= n; i++) dp[i] = dp[i - 1] + 2 * dp[i - 2]; return dp[n];}// Driver codelet n = 5;document.write("Jacobsthal number: " + Jacobsthal(n) + "<br>");document.write("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n));// This code is contributed by rameshtravel07</script> |
Output
Jacobsthal number: 11 Jacobsthal-Lucas number: 31
Time Complexity: O(n), Where n is the given number
Auxiliary Space: O(n)
Efficient approach : Space optimization O(1)
In previous approach the current value dp[i] is only depend only the previous 2 values dp[i-1] and dp[i-2]. So to optimize the space complexity we can store these values in 2 variables prev1 and prev2.
Implementation Steps:
- In both the functions we use variables prev1 and prev2 to store previous values.
- Create curr to store current value.
- Iterate over subproblems and get current value from previous values.
- At last return and print the final answer.
Implementation:
C
// A DP based solution to find Jacobsthal// and Jacobsthal-Lucas numbers#include <bits/stdc++.h>using namespace std;// Return nth Jacobsthal number.int Jacobsthal(int n){ // to store current ans previous values int curr; int prev1 , prev2; // base case prev1 = 0; prev2 = 1; // iterate to get current value from previous values for (int i = 2; i <= n; i++){ curr = prev2 + 2 * prev1; // assign values to iterate further prev1=prev2; prev2=curr; } // return answer return curr;}// Return nth Jacobsthal-Lucas number.int Jacobsthal_Lucas(int n){ // to store current ans previous values int curr; int prev1 , prev2; // base case prev1 = 2; prev2 = 1; // iterate to get current value from previous values for (int i = 2; i <= n; i++){ curr = prev2 + 2 * prev1; // assign values to iterate further prev1= prev2; prev2=curr; } // return final answer return curr;}// Driven Programint main(){ int n = 5; cout << "Jacobsthal number: " << Jacobsthal(n) << endl; cout << "Jacobsthal-Lucas number: " << Jacobsthal_Lucas(n) << endl; return 0;} |
Java
import java.util.*;public class Main { // Return nth Jacobsthal number. public static int Jacobsthal(int n) { // to store current ans previous values int curr; int prev1, prev2; if (n < 2) { return n; } // base case prev1 = 0; prev2 = 1; curr = 1; // iterate to get current value from previous values for (int i = 2; i <= n; i++) { curr = prev2 + 2 * prev1; // assign values to iterate further prev1 = prev2; prev2 = curr; } // return answer return curr; } // Return nth Jacobsthal-Lucas number. public static int Jacobsthal_Lucas(int n) { // to store current ans previous values int curr; int prev1, prev2; if (n < 2) { return n + 1; } // base case prev1 = 2; prev2 = 1; curr = 1; // iterate to get current value from previous values for (int i = 2; i <= n; i++) { curr = prev2 + 2 * prev1; // assign values to iterate further prev1 = prev2; prev2 = curr; } // return final answer return curr; } // Driven Program public static void main(String[] args) { int n = 5; System.out.println("Jacobsthal number: " + Jacobsthal(n)); System.out.println("Jacobsthal-Lucas number: " + Jacobsthal_Lucas(n)); }} |
Python3
# A DP based solution to find Jacobsthal# and Jacobsthal-Lucas numbers# Return nth Jacobsthal number.def Jacobsthal(n): # to store current ans previous values prev1, prev2 = 0, 1 # base case if n == 0: return prev1 if n == 1: return prev2 # iterate to get current value from previous values for i in range(2, n + 1): curr = prev2 + 2 * prev1 # assign values to iterate further prev1, prev2 = prev2, curr # return answer return curr# Return nth Jacobsthal-Lucas number.def Jacobsthal_Lucas(n): # to store current ans previous values prev1, prev2 = 2, 1 # base case if n == 0: return prev1 if n == 1: return prev2 # iterate to get current value from previous values for i in range(2, n + 1): curr = prev2 + 2 * prev1 # assign values to iterate further prev1, prev2 = prev2, curr # return final answer return curr# Driven Programif __name__ == '__main__': n = 5 print("Jacobsthal number:", Jacobsthal(n)) print("Jacobsthal-Lucas number:", Jacobsthal_Lucas(n)) |
Javascript
<script>// Return nth Jacobsthal number.function Jacobsthal(n) { let curr, prev1 = 0, prev2 = 1; // iterate to get current value from previous values for (let i = 2; i <= n; i++){ curr = prev2 + 2 * prev1; // assign values to iterate further prev1 = prev2; prev2 = curr; } // return answer return curr;}// Return nth Jacobsthal-Lucas number.function Jacobsthal_Lucas(n) { let curr, prev1 = 2, prev2 = 1; // iterate to get current value from previous values for (let i = 2; i <= n; i++){ curr = prev2 + 2 * prev1; // assign values to iterate further prev1 = prev2; prev2 = curr; } // return final answer return curr;}// Driver programconst n = 5;console.log(`Jacobsthal number: ${Jacobsthal(n)}`);console.log(`Jacobsthal-Lucas number: ${Jacobsthal_Lucas(n)}`);</script> |
Output:
Jacobsthal number: 11 Jacobsthal-Lucas number: 31
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
