Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is the Recaman's sequence?

Muhammad Ahmad

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

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.

The recurrence relation

In the recurrence relation of the Recaman's sequence, at least two sequences are attributed. We form the sequence aan by taking aa0 =0= 0 and letting the following:

Conditions

Recurrence relations must fulfill the following conditions:

  • Condition 1: Every term of the sequence must be positive.
  • Condition 2: The absolute difference between the term and its preceding term equal the term number nn.

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.

  • Program: Program to the nnth number in Recaman's sequence
  • Input: n = 10
  • Output: The initial terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, ...
arr(0) = 0
if n > 0 and the number is not
already included in the sequence,
arr(n) = arr(n - 1) - n //Visit the previous number in seq
else
arr(n) = arr(n - 1) + n //Visit the next number in seq
The pseudo-code for the recursive function

This pseudo-code is a function whose range is natural numbers, with 00 as the first term. Specifically, a(n)a(n) denotes the (n+1)(n+1)th term. 00 is already there.

// 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 sequence
int rec_seq(int size)
{
// Create an array to store terms
int arr[size];
// The very first term of the sequence is always 0
arr[0] = 0;
cout << arr[0]<<" ,";
int i = 1;
int j = 0;
// Generate the rest of the terms using the recursive
// formula
while(i< size)
{
int curr = arr[i-1] - i; //Visit the previous term on line
int j;
while(j < i)
{
// If arr[i-1] - i is negative or the term already exists
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i-1] + i; // Visit the next term
break;
}
j++;
}
arr[i] = curr;
cout << arr[i] << " ,";
i++;
}
}
// Driver code
int main()
{
int size = 10;
cout << "First "<< size << " terms are: " ;
rec_seq(size);
cout << "......."<<endl;
return 0;
}
A Raceman's sequence generator

Explanation

The code chunk above generates the Recaman's sequence and saves it into an array of input size nn. We only need to understand the following lines from the code.

  • Line 13: The first term of the sequence is always 00, that is, aa0 == 00
  • Line 20: This generates the previous number by arr[i - 1] - i.
  • Line 27: This checks if the number generated by line 20 is already present in the array, or if it's a negative number.
  • Line 29: If the number is negative or already present in the sequence, it generates the next number by arr[i - 1] + 1.

Use case

We can use Recamán's sequence to secure 2D images by steganography.Steganography is the practice of concealing a message within another message or a physical object.

Illustration

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.

Simulation of a Recaman's sequence

RELATED TAGS

CONTRIBUTOR

Muhammad Ahmad
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring