Recamans Sequence In C++

Recamán's sequence represents a numerical progression defined recursively, showcasing fascinating patterns and computational complexities. To derive each term, the algorithm subtracts 'n' from 'j' if the outcome is positive and not yet present in the sequence, initializing with a0 = 0. Otherwise, it adds 'n' to the previous term an−1. This sequence serves as an excellent educational tool for illustrating C++ conditionals, arrays, and recursion due to its oscillating and non-repetitive nature. Visual depictions of the sequence can unveil captivating patterns. In C++, implementing this involves efficiently monitoring utilized values using either a set or hash table, alongside employing a vector for storage purposes.

What is Recaman’s Sequence?

The initial value in Recamán's Sequence is consistently zero, with subsequent terms determined by two specific rules.

If a positive integer is not already present in the sequence, it is advisable to introduce one as the subsequent term.

Recamán's sequence is defined as follows:

• ✅ The sequence starts with a 0 =0.
• ✅ For n>0: a n =a n −1 −n, if a n −1 −n is positive and has not already appeared in the sequence. Otherwise, a n = a n −1 +n.
• ✅ a n =a n −1 −n, if a n −1 −n is positive and has not already appeared in the sequence.
• ✅ Otherwise, a n = a n −1 +n.

Example:

Input : n = 6
Output : 0, 1, 3, 6, 2, 7
Input  : n = 17
Output : 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 
         11, 22, 10, 23, 9, 24, 8

Key aspects:

• ✅ It is non-repetitive but does not completely increase or decrease.
• ✅ It is an excellent example to explain recursion, conditionals, and sequences in programming.
• ✅ Additionally, it exhibits a special set of mathematical operations and, when visualized, produces intriguing patterns that are commonly represented as arcs.

Algorithm:

1. Initialization:

• ✅ Create a blank sequence first.
• ✅ Set up a set to record the numbers that are already in the sequence.
• ✅ Set the initial term to a 0 = 0.

1. Iterate for n terms:

• ✅ Loop from i=1 to n-1.

1. Calculate the next term:

• ✅ Compute next=a i−1 +i. If next>0 and next is not in the sequence:
• ✅ Add next to the sequence. Otherwise:
• ✅ Compute next=a i−1 +i.
• ✅ Add next to the sequence.

1. Update tracking:

• ✅ Add next to the set of used numbers.

1. Repeat:

• ✅ These process continues until it generate n terms

1. Output the sequence:

• ✅ Print or return sequence.

Pseudo code:

Algorithm RecamanSequence(n):
    Initialize sequence as an empty list
    Initialize used as an empty set
    Append 0 to sequence
    Add 0 to used   
    For i from 1 to n-1:
        prev = last element of sequence
        next = prev - i       
        If next > 0 and next not in used:
            Append next to sequence
        Else:
            next = prev + i
            Append next to sequence        
        Add next to used
    Return sequence

Key features of the above algorithm:

• ✅ Effective Check: Tracking utilized values with constant-time lookups is ensured by using a set.
• ✅ Dynamic Growth: Using the recursive rule, the sequence adapts dynamically because it increases.
• ✅ Output Flexibility: The sequence can be used for additional analysis or shown.

Example:

Let's consider an example to demonstrate the Recaman’s Sequence using C++.

#include <iostream>
#include <vector>
#include <unordered_set>
void generateRecamanSequence(int n) {
    std::vector<int> sequence;
    std::unordered_set<int> used;
    // Start with the first term
    sequence.push_back(0);
    used.insert(0);  
    for (int i = 1; i < n; ++i) {
        int prev = sequence.back();
        int next = prev - i;        
        if (next > 0 && used.find(next) == used.end()) {
            sequence.push_back(next);
        } else {
            next = prev + i;
            sequence.push_back(next);
        }
        used.insert(next);
    }  
    // Print the sequence
    for (int i = 0; i < n; ++i) {
        std::cout << sequence[i] << " ";
    }
    std::cout << std::endl;
}
int main() {
    int n;
    std::cout << "Enter the number of terms in Recamán's sequence: ";
    std::cin >> n;
    generateRecamanSequence(n);  
    return 0;
}

Output:

Enter the number of terms in Recamán's sequence: 20
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62

Explanation:

• ✅ Input: The user indicates how many terms (n) to produce.
• ✅ Storage: In order to prevent repetition, a hash set keeps track of the numbers that have previously been used, while a vector saves the sequence.
• ✅ Logic: It determines whether removing i from each phrase yields a valid number. If not, the preceding phrase is increased by i.
• ✅ Output: The console displays the sequence.

Conclusion:

In summary, Recamán's sequence stands out as a novel mathematical concept that skillfully embodies the intricacy of algorithmic reasoning and recursive processes. Due to its distinctive rule-driven generation, it yields a fluctuating, non-repetitive series characterized by intriguing odd patterns that are aesthetically pleasing and intellectually stimulating. A practical approach to honing one's proficiency in fundamental programming principles such as loops, conditionals, arrays, and hash tables involves implementing Recamán's sequence in C++. Moreover, the series' captivating attributes prompt further exploration and thorough mathematical scrutiny. By employing basic arithmetic computations and adept management of previously utilized values, developers can both generate and scrutinize this sequence, showcasing the synergy between computer science and mathematics in uncovering captivating patterns.