Somos Sequence In C++

Introduction

The Somos sequence is recursively established in the realm of mathematics and is notably intriguing for its associations with elliptic curves, combinatorics, and algebraic geometry. What sets this sequence apart is its remarkable tendency to yield whole number outcomes even though it is formulated using a fractional expression.

The general form of a Somos sequence is given by:

S n =( s n-1 s n-3 +s n-2 s n-2 )/(s n-4 )

Where the starting parameters are deliberately selected as integers greater than zero.

Understanding the Somos Sequence

Let's consider an instance of Somos-4, a widely recognized iteration of the series, as illustrated below:

S n =( s n-1 s n-3 +s n-2 s n-2 )/(s n-4 )

With initial values:

S 1 =S 2 =S 3 =S 4 =1

Calculating some terms manually:

S 5 = (1X1+1 2 )/1=2

S 6 = (1X2+1 2 )/1= 3

S 7 = (2X3+1 2 )/1= 7

S 8 = (3X7+1 2 )/1= 23

It is rather unexpected that all elements in this series are whole numbers, despite the fact that the recursive definition includes fractions.

Recursive Approach

Recursive Implementation in C++

There exists a straightforward method for calculating the Somos sequence: recursion. To demonstrate the Somos Sequence in C++ through the Recursive Approach, we can consider an example.

#include <iostream>
using namespace std;

long long somos4(int n) {
    if (n <= 4) return 1;
    return (somos4(n - 1) * somos4(n - 3) + somos4(n - 2) * somos4(n - 2)) / somos4(n - 4);
}

int main() {
    int n;
    cout << "Enter the term to compute in the Somos-4 sequence: ";
    cin >> n;
    cout << "Somos-4(" << n << ") = " << somos4(n) << endl;
    return 0;
}

Output:

Problems with Recursive Solution:

• ✅ Time complexity: O(2^n), which is not feasible for large ‘n’.
• ✅ Redundant computation: Each call recomputes values that have already been computed.

Optimized Solution: Memoization

We employ memoization (a form of top-down dynamic programming) to cache previously calculated values in order to prevent inefficiencies caused by recursion. Let's consider an example to demonstrate this methodology.

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp(100, -1);
long long somos4_memo(int n) {
    if (n <= 4) return 1;
    if (dp[n] != -1) return dp[n];
    dp[n] = (somos4_memo(n - 1) * somos4_memo(n - 3) + somos4_memo(n - 2) * somos4_memo(n - 2)) / somos4_memo(n - 4);
    return dp[n];
}
int main() {
    int n;
    cout << "Enter the term to compute in the Somos-4 sequence: ";
    cin >> n;
    cout << "Somos-4(" << n << ") = " << somos4_memo(n) << endl;
    return 0;
}

Output:

Benefits of Memoization:

• ✅ Time complexity reduced from O(2^n) to O(n).
• ✅ Avoid redundant calculations: It stores previously computed values.

Iterative Dynamic Programming Approach

Instead, we have the option to remove this recursive function and develop an iterative version (bottom-up dynamic programming method) that is more effective in terms of both time and space complexity. Let's consider an illustration to demonstrate this strategy.

#include <iostream>
#include <vector>
using namespace std;

long long somos4_iterative(int n) {
    if (n <= 4) return 1;
    vector<long long> S(n + 1, 1);
    for (int i = 5; i <= n; ++i) {
        S[i] = (S[i - 1] * S[i - 3] + S[i - 2] * S[i - 2]) / S[i - 4];
    }
    return S[n];
}

int main() {
    int n;
    cout << "Enter the term to compute in the Somos-4 sequence: ";
    cin >> n;
    cout << "Somos-4(" << n << ") = " << somos4_iterative(n) << endl;
    return 0;
}

Output:

Advantages of the Iterative Approach

• ✅ Time Complexity: O(n).
• ✅ Space Complexity: O(n).
• ✅ It avoids recursive function call overhead.

Further Optimization: Space Efficient Approach

We solely require the final four computed values, enabling us to implement a rolling array method that minimizes space complexity to O(1). To better grasp this technique, let's consider an example.

#include <iostream>
using namespace std;

long long somos4_optimized(int n) {
    if (n <= 4) return 1;
    long long a = 1, b = 1, c = 1, d = 1, e;
    for (int i = 5; i <= n; ++i) {
        e = (d * b + c * c) / a;
        a = b; b = c; c = d; d = e;
    }
    return d;
}

int main() {
    int n;
    cout << "Enter the term to compute in the Somos-4 sequence: ";
    cin >> n;
    cout << "Somos-4(" << n << ") = " << somos4_optimized(n) << endl;
    return 0;
}

Output:

Final Complexity Analysis:

Conclusion:

In summary, the Somos sequence is an intriguing mathematical concept characterized by its fractional definition while maintaining integer values. Various methods were explored for calculating this sequence in C++. These included a straightforward recursive technique and a more efficient iterative solution with a constant space complexity of O(1). The latter approach stands out as the optimal implementation for practical applications.