Tutorialspoint.dev

Jacobsthal and Jacobsthal-Lucas numbers

The Jacobsthal sequence is an additive sequence similar to the Fibonacci sequence, defined by the recurrence relation Jn = Jn-1 + Jn-2, with initial terms J0 = 0 and J1 = 1. A number in the sequence is called a Jacobsthal number. They are a specific type of Lucas sequence Un(P, Q) for which P = -1 and Q = -2.
The first Jacobsthal numbers are:
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, ……

Jacobsthal numbers are defined by the recurrence relation:
{displaystyle J_{n}=left{egin{matrix} 0   &   &  if n=0\1&&ifn=1  \ J_{n-1} + 2J_{n-2}&&ifn>1  end{matrix}
ight.}

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:{displaystyle L_{n}=left{egin{matrix} 2   &   &  if n=0\1&&ifn=1  \ L_{n-1} + 2L_{n-2}&&ifn>1  end{matrix}
ight.}

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.util.*;
import java.lang.*;
  
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 cotributed 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 cotributed 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) , " ";
echo "Jacobsthal-Lucas number: "
      Jacobsthal_Lucas($n), " ";
  
// This code is contributed by aj_36 
?>


Output :

Jacobsthal number: 11
Jacobsthal-Lucas number: 31

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.util.*;
import java.lang.*;
  
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 cotributed 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 cotributed 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), " ";
echo "Jacobsthal-Lucas number: " ,
       Jacobsthal_Lucas($n), " ";
          
// This code is contributed by ajit
?>


Output:

Jacobsthal number: 11
Jacobsthal-Lucas number: 31


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter