## The Recamán Sequence

### May 10, 2019

This is easy. We keep track of the numbers previously seen in the sequence using a bit-array that grows as necessary:

```(define-generator (recaman)
(let ((bits (vector 0)) (len 8))
(define (bit-set! n)
(when (<= len n)
(let ((new-bits (make-vector (/ len 4) 0)))
(do ((i 0 (+ i 1))) ((= i (/ len 8)))
(vector-set! new-bits i (vector-ref bits i)))
(set! len (+ len len))
(set! bits new-bits)))
(let ((index (quotient n 8)) (offset (modulo n 8)))
(vector-set! bits index
(bitwise-ior (bitwise-arithmetic-shift-left 1 offset)
(vector-ref bits index)))))
(define (bit-get n)
(let ((index (quotient n 8)) (offset (modulo n 8)))
(bitwise-and
(bitwise-arithmetic-shift-right
(vector-ref bits index)
offset)
1)))
(let loop ((pos 0) (gap 1))
(bit-set! pos) (yield pos)
(let ((t (if (and (not (negative? (- pos gap)))
(zero? (bit-get (- pos gap))))
(- pos gap)
(+ pos gap))))
(loop t (+ gap 1)))))))```

The bit-array grows by doubling the available space, because that makes the amortized cost of accessing each element constant; growing by a single item at each step would make our algorithm quadratic. We only have to worry about growth when setting a bit because getting a bit always works to the left of our current position. Here are some examples of both the Recaman:

```> (gen-take 25 (recaman))
(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)
> (gen-ref (recaman) 1000)
3686
> (gen-ref (recaman) 1000000)
2057164```

You can run the program at https://ideone.com/WqasCC.

Pages: 1 2

### 3 Responses to “The Recamán Sequence”

1. Zack said

Interesting problem. Here is my take using Julia:

function recaman(n::Int64)
R = Array{Int64}(undef, n)
R = 1

``````for i = 2:n
if i % 10000 == 0; print(i, "\t"); end # something to keep track of the progress made
x = R[i-1] - i

if (x < 2)||(x in R[2:(i-2)])
R[i] = R[i-1] + i
else
R[i] = x
end
end

return R[n]
``````

end

2. Paul said

In Python.

```from itertools import count, islice

def recaman():
S, x = set(), 0
for n in count(1):
yield x
xmin = x - n
x = xmin if xmin > 0 and xmin not in S else x + n

N = 1000000
r = recaman()
next(islice(r, N, N), None)  # skip N terms
print(next(r))  # -> 2057164```
3. Daniel said

Here’s a solution in C++.

```#include <cstdlib>
#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main(int argc, char* argv[]) {
if (argc != 2) return EXIT_FAILURE;
int n = stoi(argv);
unordered_set<int> set({0});
int R = 0;
for (int i = 1; i <= n; ++i) {
R -= i;
if (R < 0 || set.find(R) != set.end())
R += 2 * i;
set.insert(R);
}
cout << R << endl;
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 1000000
2057164
```