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

Interesting problem. Here is my take using Julia:

function recaman(n::Int64)

R = Array{Int64}(undef, n)

R[1] = 1

end

answer: 2057164

Enjoy your weekend!

In Python.

Here’s a solution in C++.

Example Usage: