Home Â» Recamans Sequence

# Recamanâ€™s Sequence

RecamÃ¡nâ€™s sequence recurrence relation in mathematics and computer science. Because its elements are clearly related to the previous elements, they are frequently defined using recursion.

## Definition

The RecamÃ¡nâ€™s sequence a0, a1, a2 is defined as:

The first terms of the sequence are:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157, 224, 156, 225, 155, â€¦

Print the first n elements of Recamanâ€™s sequence given an integer n.

Examples:

It is essentially a function with domain and co-domain as natural numbers and 0 respectively. It is defined recursively as follows:

Make a(n) to denote the (n+1)-th term. (0 is already present).

According to Rules:

A simple implementation is shown below, in which we store all n Recaman Sequence numbers in an array. Using the recursive formula mentioned above, we compute the next number.

### C++

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, allowing us to run this programme in O(n) time.

### C++

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)

## Uses

RecamÃ¡nâ€™s sequence, in addition to its mathematical and aesthetic properties, can be used to encrypt 2D images using steganography.

Next Topic#