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.
Programming Praxis 
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.
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)) # -> 2057164Here’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: