Tutorialspoint.dev

Recaman’s sequence

Given an integer n. Print first n elements of Recaman’s sequence.

Examples:

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

It is basically a function with domain and co-domain as natural numbers and 0. It is recursively defined as below:
Specifically, let a(n) denote the (n+1)-th term. (0 being already there).
The rule says:

a(0) = 0,
if n > 0 and the number is not 
   already included in the sequence,
     a(n) = a(n - 1) - n 
else 
     a(n) = a(n-1) + n. 



Below is simple implementation where we store all n Recaman Sequence numbers in an array. We compute next number using recursive formula mentioned above.

C++

// C++ program to print n-th number in Recaman's 
// sequence
#include <bits/stdc++.h>
using namespace std;
  
// Prints first n terms of Recaman sequence
int recaman(int n)
{
    // Create an array to store terms
    int arr[n];
  
    // First term of the sequence is always 0
    arr[0] = 0;
    printf("%d, ", arr[0]);
  
    // Fill remaining terms using recursive
    // formula.
    for (int i=1; i< n; i++)
    {
        int curr = arr[i-1] - i;
        int j;
        for (j = 0; j < i; j++)
        {
            // If arr[i-1] - i is negative or
            // already exists.
            if ((arr[j] == curr) || curr < 0)
            {
                curr = arr[i-1] + i;
                break;
            }
        }
  
        arr[i] = curr;
        printf("%d, ", arr[i]);
    }
}
  
// Driver code
int main()
{
    int n = 17;
    recaman(n);
    return 0;
}

Java

// Java program to print n-th number in Recaman's 
// sequence
import java.io.*;
  
class GFG {
      
    // Prints first n terms of Recaman sequence
    static void recaman(int n)
    {
        // Create an array to store terms
        int arr[] = new int[n];
      
        // First term of the sequence is always 0
        arr[0] = 0;
        System.out.print(arr[0]+" ,");
      
        // Fill remaining terms using recursive
        // formula.
        for (int i = 1; i < n; i++)
        {
            int curr = arr[i - 1] - i;
            int j;
            for (j = 0; j < i; j++)
            {
                // If arr[i-1] - i is negative or
                // already exists.
                if ((arr[j] == curr) || curr < 0)
                {
                    curr = arr[i - 1] + i;
                    break;
                }
            }
      
            arr[i] = curr;
            System.out.print(arr[i]+", ");
              
        }
    }
      
    // Driver code
    public static void main (String[] args) 
    {
        int n = 17;
        recaman(n);
  
    }
}
  
// This code is contributed by vt_m

Python 3

# Python 3 program to print n-th
# number in Recaman's sequence
  
# Prints first n terms of Recaman
# sequence
def recaman(n):
  
    # Create an array to store terms
    arr = [0] * n
  
    # First term of the sequence
    # is always 0
    arr[0] = 0
    print(arr[0], end=", ")
  
    # Fill remaining terms using
    # recursive formula.
    for i in range(1, n):
      
        curr = arr[i-1] - i
        for j in range(0, i):
          
            # If arr[i-1] - i is
            # negative or already
            # exists.
            if ((arr[j] == curr) or curr < 0):
                curr = arr[i-1] + i
                break
              
        arr[i] = curr
        print(arr[i], end=", ")
  
# Driver code
n = 17
  
recaman(n)
  
# This code is contributed by Smitha.

C#

// C# program to print n-th number in Recaman's 
// sequence
using System;
  
class GFG {
      
    // Prints first n terms of Recaman sequence
    static void recaman(int n)
    {
        // Create an array to store terms
        int []arr = new int[n];
      
        // First term of the sequence is always 0
        arr[0] = 0;
        Console.Write(arr[0]+" ,");
      
        // Fill remaining terms using recursive
        // formula.
        for (int i = 1; i < n; i++)
        {
            int curr = arr[i - 1] - i;
            int j;
            for (j = 0; j < i; j++)
            {
                // If arr[i-1] - i is negative or
                // already exists.
                if ((arr[j] == curr) || curr < 0)
                {
                    curr = arr[i - 1] + i;
                    break;
                }
            }
      
            arr[i] = curr;
        Console.Write(arr[i]+", ");
              
        }
    }
      
    // Driver code
    public static void Main () 
    {
        int n = 17;
        recaman(n);
  
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP program to print n-th
// number in Recaman's sequence
  
// Prints first n terms 
// of Recaman sequence
function recaman($n)
{
      
    // First term of the 
    // sequence is always 0
    $arr[0] = 0;
    echo $arr[0], ", ";
  
    // Fill remaining terms 
    // using recursive formula.
    for ($i = 1; $i < $n; $i++)
    {
            $curr = $arr[$i - 1] - $i;
            $j;
        for ($j = 0; $j < $i; $j++)
        {
              
            // If arr[i-1] - i
            // is negative or
            // already exists.
            if (($arr[$j] == $curr) || $curr < 0)
            {
                $curr = $arr[$i-1] + $i;
                break;
            }
        }
  
        $arr[$i] = $curr;
        echo $arr[$i], ", ";
    }
}
  
    // Driver Code
    $n = 17;
    recaman($n);
      
// This code is contributed by Ajit
?>


Output:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 

Time Complexity : O(n2)
Auxiliary Space : O(n)

 

Optimizations :
We can use hashing to store previously computed values and can make this program work in O(n) time.

C++

// C++ program to print n-th number in Recaman's 
// sequence
#include <bits/stdc++.h>
using namespace std;
  
// Prints first n terms of Recaman sequence
void recaman(int n)
{
    if (n <= 0)
      return;
  
    // Print first term and store it in a hash 
    printf("%d, ", 0);
    unordered_set<int> s;
    s.insert(0);
  
    // Print remaining terms using recursive
    // formula.
    int prev = 0;
    for (int i=1; i< n; i++)
    {
        int curr = prev - i;
  
        // If arr[i-1] - i is negative or
        // already exists.
        if (curr < 0 || s.find(curr) != s.end())
           curr = prev + i;
  
        s.insert(curr);
  
        printf("%d, ", curr);
        prev = curr;
    }
}
  
// Driver code
int main()
{
    int n = 17;
    recaman(n);
    return 0;
}

Python3

# Python3 program to print n-th number in
# Recaman's sequence
  
# Prints first n terms of Recaman sequence
def recaman(n):
  
    if(n <= 0):
        return
  
    # Print first term and store it in a hash
    print(0, ",", end='')
    s = set([])
    s.add(0)
  
    # Print remaining terms using recursive
    # formula.
    prev = 0
    for i in range(1, n):
  
        curr = prev - i
  
        # If arr[i-1] - i is negative or
        # already exists.
        if(curr < 0 or curr in s):
            curr = prev + i
  
        s.add(curr)
  
        print(curr, ",", end='')
        prev = curr
  
# Driver code
if __name__=='__main__':
    n = 17
    recaman(n)
  
# This code is contributed by
# Sanjit_Prasad

PHP


Output:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 

Time Complexity : O(n)
Auxiliary Space : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter