Somos Sequence in C++

Introduction

The Somos sequence is recursively defined in mathematics and is extremely interesting for its connections to elliptic curves, combinatorics, and algebraic geometry. The strange thing about this sequence is its propensity to result in integer values despite being defined by a fraction.

The general form of a Somos sequence is given by:

S_n=( s_n-1s_n-3+s_n-2s_n-2)/(s_n-4)

Where the initial conditions are carefully chosen positive integers.

Understanding the Somos Sequence

Let’s take an example of Somos-4, a well-known version of the sequence, which follows:

S_n=( s_n-1s_n-3+s_n-2s_n-2)/(s_n-4)

With initial values:

S₁=S₂=S₃=S₄=1

Calculating some terms manually:

S₅ = (1X1+1²)/1=2

S₆ = (1X2+1²)/1= 3

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

S₈ = (3X7+1²)/1= 23

It is quite surprising because all terms of this sequence are integers, while the recursive definition involves fractions.

Recursive Approach

Recursive Implementation in C++

There is a simple way to compute the Somos sequence: recursion. Let us take an example to illustrate the Somos Sequence in C++ using the Recursive Approach.

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 use memoization (top-down dynamic programming) to store previously computed values to avoid recursion inefficiencies. Let us take an example to illustrate this approach.

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 can eliminate this recursion and build an iterative variant (bottom-up dynamic programming approach), which is more efficient using both time complexity and space. Let us take an example to illustrate this approach.

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 only need the last four computed values, which allows us to use a rolling array approach to reduce space to O(1). Let us take an example to illustrate this approach.

Output:

Final Complexity Analysis:

Conclusion:

In conclusion, the Somos sequence is a strange construct from mathematics that is defined fractionally but remains integer-valued. We considered several approaches to computing it in C++. One was the naive recursive approach, and another was an optimized iterative version with a space complexity of O(1). This last version is the best implementation for actual use.