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.

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “The Recamán Sequence”

Zack said

May 10, 2019 at 10:14 AM

Interesting problem. Here is my take using Julia:

function recaman(n::Int64)
R = Array{Int64}(undef, n)
R[1] = 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

answer: 2057164

Enjoy your weekend!

Paul said

May 10, 2019 at 11:14 AM

In Python.

from itertools import count, islice

def recaman():
    S, x = set(), 0
    for n in count(1):
        S.add(x)
        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

Daniel said

June 30, 2019 at 8:17 PM

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[1]);
  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

Programming Praxis