Jacobsthal and Jacobsthal-Lucas numbers

0 0 11 minutes read

Jacobsthal numbers

The Jacobsthal numbers are the numbers obtained by the U_ns 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:

$J_{n}=\left\{\begin{matrix} 0 & & if n=0\\1&&ifn=1 \\ J_{n-1} + 2J_{n-2}&&ifn>1 \end{matrix}\right.$

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 V_n(1, -2). They satisfy the same recurrence relation as Jacobsthal numbers but have different initial values:

$L_{n}=\left\{\begin{matrix} 2 & & if n=0\\1&&ifn=1 \\ L_{n-1} + 2L_{n-2}&&ifn>1 \end{matrix}\right.$

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: 31

Input : 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 Program
int 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 numbers
import 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 Program
n = 5
print("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 numbers
using 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 Program
int 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 numbers
import 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 Program
n = 5
 
print("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 numbers
using 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 code
let 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 Program
int 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 Program
if __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 program
const 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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!