Recamán's sequence

(2 comments)

The Recamán sequence is a famous sequence invented by the Colombian mathematician, Bernardo Recamán Santos. It is defined by the following algorithm, starting at $a_0 = 0$:

$a_n = a_{n-1} - n$ if this number is positive and has not already appeared in the sequence; otherwise $a_n = a_{n-1} + n$.

It was covered in a Numberphile YouTube video that also featured the visualization by Edmund Harriss in which sequential numbers are linked by semicircular arcs. The following Python code reproduces the resulting image.

The Recamán sequence up to n=60

The test for deciding the next number in the sequence uses Python's new (since 3.8) "Walrus operator". This allows the use of a named expression: (b := a - n) in the conditional statement:

if (b := a - n) > 0 and b not in seen:
    a = b

which assigns the result of a - n to the variable name b so that its value can be reused. In Python 3.7 and earlier, the assignment has to be made on a separate line:

b = a - n
if b > 0 and b not in seen:
    a = b

I'm not wild about named expressions, and wouldn't usually use one in my own code here; I find the second approach clearer and less error prone: if you forget the parentheses, the line if b := a - n > 0 and b not in seen: is syntactically correct but assigns the boolean result of a - n > 0 to b because of the higher precedence of the > operator...

import numpy as np
import matplotlib.pyplot as plt

# Equal aspect ratio Figure with black background and no axes.
fig, ax = plt.subplots(facecolor='k')
ax.axis('equal')
ax.axis('off')

# Colour the lines sequentially from a Matplotlib colormap.
cm = plt.cm.get_cmap('Spectral')

def add_to_plot(lasta, a, n):
    """Add a semi-circular arc from a to lasta.

    Arcs alternate to be above and below the x-axis according to whether
    n is even or odd.

    """

    # Arc centre and radius.
    c, r = (a + lasta) / 2, abs(a - lasta) / 2
    x = np.linspace(-r, r, 1000)
    y = np.sqrt(r**2 - x**2) * (-1)**n
    color = cm(n/max_terms)
    ax.plot(x+c, y, c=color, lw=1)

# Keep track of which numbers have been "visited" in this set.
seen = set()
n = a = 0
lasta = None
max_terms = 60
while n < max_terms:
    lasta = a
    if (b := a - n) > 0 and b not in seen:
        a = b
    else:
        a = a + n
    seen.add(a)
    n += 1
    print(a)
    add_to_plot(lasta, a, n)

plt.show()

If you like your Recamán sequence visualized diagonally, modify the add_to_plot function to rotate by 45°:

def add_to_plot(lasta, a, n):
    c = (a + lasta) / 2
    r = abs(a - lasta) / 2
    x = np.linspace(-r, r, 1000)
    y = np.sqrt(r**2 - x**2) * (-1)**n
    color = cm(n/max_terms)
    X = x+c
    f = np.sqrt(2)
    ax.plot((X-y)*f, (X+y)*f, c=color, lw=1)

The Recamán sequence visualized along a diagonal

Current rating: 4.8

Comments

Comments are pre-moderated. Please be patient and your comment will appear soon.

Nathan 3 months, 3 weeks ago

Thank you so much for your contribution. I love your website and the beautiful artsy examples you show here.

Link | Reply
Currently unrated

christian 3 months, 3 weeks ago

Thank you very much! I'm glad you like them.

Link | Reply
Currently unrated

New Comment

required

required (not published)

optional

required