Programming Praxis

3 Responses to “The Recamán Sequence”

1. 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!
2. 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
3. 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