Jacobsthal Numbers In C++

Introduction:

We often come across the Fibonacci numbers in the domain of number sequences, but the Jacobsthal numbers present another captivating sequence. While not as popular, this series possesses unique characteristics and applications in various areas such as circuit design, computer science, and cryptography. In the following content, we will delve into the Jacobsthal numbers, their attributes, and demonstrate their implementation in the C++ programming language.

What are Jacobsthal Numbers?

Jacobsthal numbers create a series in which each subsequent number is generated based on a defined recurrence relationship:

Jn = Jn-1 + 2 × Jn-2

The sequence starts with the following values:

• ✅ J(0) = 0
• ✅ J(1) = 1
• ✅ J(2) = J(1) + 2 × J(0) = 1 + 0 = 1
• ✅ J(3) = J(2) + 2 × J(1) = 1 + 2 × 1 = 3
• ✅ J(4) = J(3) + 2 × J(2) = 3 + 2 × 1 = 5
• ✅ J(5) = J(4) + 2 × J(3) = 5 + 2 × 3 = 11
• ✅ J(6) = J(5) + 2 × J(4) = 11 + 2 × 5 = 21

Thus, the sequence follows:

0, 1, 1, 3, 5, 11, 21, 43, 85, 171, ...

This arrangement of numbers adds an intriguing aspect to the Jacobsthal sequence, particularly in relation to binary calculations.

Applications of Jacobsthal Numbers:

Several applications of Jacobsthal numbers in C++ are as follows:

• ✅ Binary and Gray Code Conversions: The sequence helps in designing efficient Gray code sequences used in error detection and digital communication.
• ✅ Fibonacci-like Computations: The recurrence relation resembles Fibonacci numbers but with a different multiplier, which leads to unique applications in recurrence-based algorithms.
• ✅ Graph Theory and Counting Problems: It is used in combinatorial problems involving paths and trees.

Implementing in C++:

Let's investigate various methods for calculating the Jacobsthal numbers using C++.

1. Recursive Approach

A direct method involves utilizing recursion, akin to the concept of Fibonacci numbers.

#include <iostream>
using namespace std;
// Function to compute Jacobsthal numbers recursively
int jacobsthal(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return jacobsthal(n - 1) + 2 * jacobsthal(n - 2);
}
int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "Jacobsthal number at position " << n << " is " << jacobsthal(n) << endl;
    return 0;
}

Output:

Enter the value of n: 25
Jacobsthal number at position 25 is 11184811

2. Memoization (Top-Down Dynamic Programming)

Although recursion is straightforward to grasp, it becomes inefficient when dealing with large values of n. To address this issue, we can enhance its performance by implementing memoization. This technique involves storing precomputed values to prevent repetitive computations.

#include <iostream>
#include <vector>
using namespace std;
vector<int> dp(100, -1);
int jacobsthal_memo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (dp[n] != -1) return dp[n]; // Use cached value
    dp[n] = jacobsthal_memo(n - 1) + 2 * jacobsthal_memo(n - 2);
    return dp[n];
}
int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "Jacobsthal number at position " << n << " is " << jacobsthal_memo(n) << endl;
    return 0;
}

Output:

Enter the value of n: 18
Jacobsthal number at position 18 is 87381

3. Iterative Dynamic Programming (Bottom-Up Approach)

This method eliminates the need for recursive processing, resulting in enhanced performance.

#include <iostream>
using namespace std;
int jacobsthal_iterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;  
    int prev2 = 0, prev1 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + 2 * prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}
int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "Jacobsthal number at position " << n << " is " << jacobsthal_iterative(n) << endl;
    return 0;
}

Output:

Enter the value of n: 4
Jacobsthal number at position 4 is 5

4. Using Matrix Exponentiation (Optimized for Large n)

The recursive formula can be depicted as a matrix, enabling the calculation of Jacobsthal numbers efficiently through the process of matrix exponentiation.

#include <iostream>
using namespace std;
void multiply(int F[2][2], int M[2][2]) {
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];  
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
void power(int F[2][2], int n) {
    if (n == 0 || n == 1) return;
    int M[2][2] = {{1, 2}, {1, 0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2) multiply(F, M);
}
int jacobsthal_matrix(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int F[2][2] = {{1, 2}, {1, 0}};
    power(F, n - 1);
    return F[0][0];
}

// Main function to test the implementation
int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "Jacobsthal number J(" << n << ") = " << jacobsthal_matrix(n) << endl;
    return 0;
}

Output:

Enter the value of n: 9
Jacobsthal number J(9) = 171

Conclusion

Jacobsthal numbers present a fascinating numeric series that finds utility in different scenarios. We investigated diverse techniques for calculating these numbers in C++, ranging from basic recursion to more optimized approaches such as matrix exponentiation.