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−1n if Rn = Rn−1n 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.

Advertisements

Pages: 1 2

2 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

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: