Find The Pell Number Using C++

When it comes to numerical patterns, the Fibonacci sequence and the Pell numbers sequence share a comparable recursive relationship. The Pell numbers are characterized by the following recurrence relation.

p(n)=2*p(n-1)+p(n-2)

With their initial values are p(0)=0 & p(1)=1 .

Retrieve the initial Pell numbers which include 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461,... Develop a function named int pell(int n) designed to provide the P n value.

Example:

Input : n = 2
Output :1
Input  : n = 9
Output : 985
Input  : n = 13
Output : 33461

To locate Pell numbers in C++, a straightforward algorithm can be crafted to traverse the sequence and compute each Pell number by referencing the two preceding Pell numbers. This algorithm can be executed in two distinct manners: either recursively or iteratively.

Approach 1: Recursive Approach

Let's consider a demonstration to explain the pell number in C++ utilizing a Recursive Approach.

#include <iostream>

using namespace std;

// Function to calculate the nth Pell number recursively
int calculatePellNumber(int n) {
    // Base cases for n = 0 and n = 1
    if (n <= 1)
        return n;
    
    // Recursive calculation using the Pell number recurrence relation
    return 2 * calculatePellNumber(n - 1) + calculatePellNumber(n - 2);
}

int main() {
    int position; // Position of the Pell number to find
    cout << "Enter the position of the Pell number to find: ";
    cin >> position; // Input position from the user
    
    // Calculate and output the Pell number at the given position
    cout << "The Pell number at position " << position << " is: " << calculatePellNumber(position) << endl;
    
    return 0;
}

Output:

Enter the position of the Pell number to find: 8
The Pell number at position 8 is: 408

Explanation:

In order to use recursion, we calculatePellNumber (n-1) && calculatePellNumber (n-2) until n is equal to or less than 2 because we are aware that the pell numbers up to 2 are the same as the input. O(N) , where N is the specified number, is the overall time complexity of the program mentioned above.

• ✅ The Pell number recurrence relation is used by the function calculatePellNumber to recursively calculate the nth Pell number.
• ✅ In order to find the Pell number's position, the primary function requests input from the user.
• ✅ After passing in the input position, it invokes the calculatePellNumber function and outputs the outcome.

Approach 2: Iterative Approach

Let's consider an example to demonstrate the Pell number in C++ using an iterative method.

#include <iostream>

using namespace std;

int main() {
    int position = 10; // Given position to find the Pell number.
    int prevPrevPell = 0; // Initial value of P(n-2).
    int prevPell = 1; // Initial value of P(n-1).
    int currentPell; // Placeholder for the current Pell number.

    // If the given position is less than or equal to 2, the Pell number is the same as the position.
    if (position <= 2) {
        cout << "Pell number at position " << position << ": " << position << endl;
    } else {
        // Loop to find Pell number at the given position using iteration.
        for (int i = 2; i <= position; i++) {
            currentPell = 2 * prevPell + prevPrevPell;
            prevPrevPell = prevPell; // Update P(n-2) for the next iteration.
            prevPell = currentPell; // Update P(n-1) for the next iteration.
        }

        cout << "Pell number at position " << position << ": " << currentPell << endl;
    }

    return 0;
}

Output:

Pell number at position 10: 2378

Explanation:

We are traversing from 2 to n in the provided program to update the values for prevprevPell (n-2) to prevPell (n-1) and prevPell n-1 to currentPell until we reach n.

• ✅ The position variable denotes the postion to find the pell number.
• ✅ P(n-2) represents the "PREVPREVPELL" number which is initialized to 0.
• ✅ P(n-1) represents the "PREVPELL" number which is initialized to 1.
• ✅ The loop determines the Pell number by iterating from the second number to the specified position.
• ✅ Using the Pell number recurrence relation, the current Pell number is updated.
• ✅ Lastly, printing of the Pell number at the specified position is done.

Conclusion:

The puzzle involving the Nth Pell number was successfully tackled by employing both recursion and iteration. Furthermore, we were instructed on how to implement a C++ solution for the problem, detailing both the Standard and Optimized approaches. This particular solution can be adapted to multiple programming languages including C, Java, Python, and more.