The Recamán Sequence
May 10, 2019
I’ve been watching Numberphile again, specifically their episode about the Recamán sequence 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, … A005132, defined as follows:
The Recamán sequence is an integer sequence R with R0 = 0 and Rn = Rn−1 − n if Rn = Rn−1 − n is positive and not already in the sequence and Rn−1 + n otherwise.
Your task is to write a program that generates the Recamán sequence; use your program to compute R1000000 (the one-million-and-first element). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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: