Recamans Sequence In C++

Recamán's sequence is a mathematical series with a recursive definition that poses intriguing patterns and computational challenges. Each term j is calculated by subtracting n from j if the result is positive and not already in the series, starting with a0 = 0. If not, n is added to an−1. The sequence is ideal for teaching C++ conditionals, arrays , and recursion since it is oscillatory and non-repetitive. Visual representations of the series can reveal intriguing patterns. It is accomplished in C++ using a set or hash table to efficiently track used values and a vector for storage.

What is Recaman’s Sequence?

The first term of Recamán's Sequence is always zero. Two rules determine the next term.

If it isn't already in the series, we should use a positive integer as the next 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:

Example
Copy
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
Try it Yourself

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:

Example
Copy
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
Try it Yourself

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 us take an example to illustrate the Recaman’s Sequence in 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 conclusion, Recamán's sequence is an innovative mathematical invention that perfectly captures the elegance of algorithmic logic and recursion. Because of its unique rule-based creation, it produces an oscillating, non-repetitive sequence with odd patterns that are both visually appealing and computationally engaging. A useful way to practice using basic programming concepts like loops, conditionals, arrays, and hash tables is to use Recamán's sequence in C++. Furthermore, the series' fascinating qualities encourage deeper investigation and in-depth mathematical analysis. Using straightforward arithmetic operations and effective handling of previously used numbers, programmers can create and analyze this series, demonstrating how computer science and mathematics can work together to find fascinating patterns.