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.

Advertisements

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] = 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!

  2. Paul said

    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
  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[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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: