The Recaman's sequence is named after its inventor, Bernardo Recaman. It's a well-known sequence that is defined by the recurrence relation. We can define it by recursion.
In the recurrence relation of the Recaman's sequence, at least two sequences are attributed. We form the sequence
Recurrence relations must fulfill the following conditions:
In the recurrence relation, we subtract, or visit the previous term, if we can. Otherwise, we add, or visit next term. We'll understand this by seeing some initial terms.
Let's generate this sequence through C/C++ program.
n
= 10
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, ...
arr(0) = 0if n > 0 and the number is notalready included in the sequence,arr(n) = arr(n - 1) - n //Visit the previous number in seqelsearr(n) = arr(n - 1) + n //Visit the next number in seq
This pseudo-code is a function whose range is natural numbers, with
// This program prints n-th number of the Recaman's sequence#include <iostream>using namespace std;// The function prints the first n terms of the Recaman's sequenceint rec_seq(int size){// Create an array to store termsint arr[size];// The very first term of the sequence is always 0arr[0] = 0;cout << arr[0]<<" ,";int i = 1;int j = 0;// Generate the rest of the terms using the recursive// formulawhile(i< size){int curr = arr[i-1] - i; //Visit the previous term on lineint j;while(j < i){// If arr[i-1] - i is negative or the term already existsif ((arr[j] == curr) || curr < 0){curr = arr[i-1] + i; // Visit the next termbreak;}j++;}arr[i] = curr;cout << arr[i] << " ,";i++;}}// Driver codeint main(){int size = 10;cout << "First "<< size << " terms are: " ;rec_seq(size);cout << "......."<<endl;return 0;}
The code chunk above generates the Recaman's sequence and saves it into an array of input size
arr[i - 1] - i
.arr[i - 1] + 1
.We can use Recamán's sequence to secure 2D images by
Neil Sloane has conjectured that every number eventually appears, but this has not been proved. The illustration below will give us an idea of how the algorithm produces a sequence by moving backward and forward on a number line.
Free Resources