Sterns Diatomic Sequence Number In C++

In this tutorial, we will explore Stern's diatomic series index in C++ along with its methodology, a demonstration, time efficiency, and memory usage analysis.

Stern’s diatomic sequence:

Stern's diatomic series represents a set of whole numbers that demonstrates a strong connection to the Calkin-Wilf tree and adheres to a specific recursive pattern. The progression of this sequence is as follows:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …

This series, commonly referred to as the fusc function, holds significance across various fields such as combinatorics and number theory.

The Calkin-Wilf binary tree in mathematics is a unique tree structure where each node corresponds to a distinct positive rational number. The children of the tree's nodes are defined by the formulas 1/1+1/q=a/a+b and q+1=a+b/b, originating from the root node 1, with q denoting any rational number that can be expressed in its simplest form as b/a.

All affirmative rational numbers are guaranteed to be present only once in the tree thanks to this. Kepler's Harmonices Mundi stands out as one of the initial pieces of literature to integrate this idea, known as the Neil Calkin and Herbert Wilf principle.

Traversing this tree in a breadth-first manner generates the Calkin–Wilf sequence. It's worth mentioning that the fusc function is capable of efficiently calculating Stern's diatomic series, which corresponds to the sequence of numerators (or denominators, when adjusted by one) during this traversal.

Stern's Diatomic Sequence, represented by P(n), is specified recursively in the following manner:

Base Cases:

P(0)=0,P(1)=1

Recurrence Relations:

If n is even:

P(n)=P(n/2)

If n is odd:

P(n)=P((n−1)/2)+P((n+1)/2)

This progression holds significance in the field of number theory and finds applications in Farey sequences and continued fractions. Stern's Diatomic Sequence begins with the initial values of 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ...

Approach:

Similar to the process of computing Fibonacci numbers, Dynamic Programming (DP) can be employed to address this issue efficiently. Initially, we establish a DP array where the initial values are DP[0] = 0 and DP[1] = 1. Subsequently, we progress through the array from i = 2 to n, calculating each DP[i] using the Stern’s Diatomic Sequence recurrence relation:

If i is even, we use:

P[i]=P[i/2]

If i is odd, we use:

P[i]=P[(i−1)/2]+P[(i+1)/2]

To achieve a time complexity of O(n), we prevent redundant calculations by storing previously computed values. The ultimate outcome, P[n], effectively yields the required element in the sequence.

Algorithm:

Let us take an algorithm.

P[0] = 0;
P[1] = 1;
for (int q = 2; q <= n; q++)
 {
    if (q % 2 == 0)
        P[q] = P[q / 2];
    else
        P[q] = P[(q - 1) / 2] + P[(q + 1) / 2];
}
return P[n];

Example:

Let's consider an example to demonstrate Stern's diatomic sequence index in C++.

#include <iostream>
#include <vector>
using namespace std;
// Function to compute the nth element of Stern's Diatomic Sequence
int computeSternDiatomic(int number) 
{
    // Dynamic programming array to store computed values
    vector<int> sequence(number + 1, 0);
    // Base cases
    sequence[0] = 0;
    sequence[1] = 1;
    // Compute the sequence iteratively
    for (int i = 2; i <= number; i++)
    {
        if (i % 2 == 0)
        {
            sequence[i] = sequence[i / 2]; // Even case
        } 
        else
        {
            sequence[i] = sequence[(i - 1) / 2] + sequence[(i + 1) / 2]; // Odd case
        }
    }
    return sequence[number];
}
int main()
{
    int userInput;
    // Taking input from the user
    cout << "Enter the value of n: ";
    cin >> userInput;
    // Validate input
    if (userInput < 0)
    {
        cout << "Invalid input! Please enter a non-negative integer." << endl;
        return 1;
    }
    // Compute and display the nth Stern's Diatomic Sequence number
    int result = computeSternDiatomic(userInput);
    cout << "The " << userInput << "th element of Stern's Diatomic Sequence is: " << result << endl;
    return 0;
}

Output:

Enter the value of n: 15
The 15th element of Stern's Diatomic Sequence is: 4

Complexity Analysis:

• ✅ Time Complexity: O(N) - The algorithm computes each value in constant time utilizing previously stored results as it iterates from 2 to N, resulting in a linear time complexity.
• ✅ Auxiliary Space: O(N) - Computed values are stored in a DP array of size N+1, which takes up O(N) more space.

Explanation:

The provided program in C++ utilizes dynamic programming to effectively determine the nth element of Stern's Diatomic Sequence. To prevent the exponential growth associated with a recursive approach, it achieves O(n) time complexity by initializing a vector for storing precomputed values. The sequence follows the recurrence relation: S(n) = S(n-1)/2) + S((n+1)/2) for odd indices and S(n) = S(n/2) for even indices. Upon verifying user input to prevent negative values, the program proceeds to calculate the corresponding sequence element. If the input is invalid, an error message is displayed, and a nonzero status is returned. Otherwise, the result is presented in a structured output format. By minimizing redundant computations, the algorithm ensures efficient processing.