Recamán’s Sequence

Adam Rumpf, 8/25/2018

Introduction

Recamán’s sequence starts at index n=0 with element (Subscript[a, 0])=0. To find (Subscript[a, n+1]) given (Subscript[a, n]), we either take n steps backward or n steps forward. We go backward if (Subscript[a, n])-n is (a) nonnegative and (b) not already part of the sequence. Otherwise we go forward.

Starting from (Subscript[a, 0])=0, our choices for (Subscript[a, 1]) are to go backward to -1 or forward to 1. We only allow nonnegative entries, so we take (Subscript[a, 1])=1. Next we go either 2 steps backward to 0 or 2 steps forward to 3. 0 is already on our list, so we go forward to get (Subscript[a, 2])=3. For (Subscript[a, 3]) our choices are 0 or 6, so we take (Subscript[a, 3])=6. For (Subscript[a, 4]) our choices are 2 or 10, and since 2 is not yet on our list, we go backwards to (Subscript[a, 4])=2. The first 10 elements are:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, ...

The common way to "picture" Recamán's sequence is to draw semicircles on the number line, alternating over/under to connect pairs of consecutive values. Given the values in the sequence, we can generate the shapes with the Circle function.

Code

Initialization

(* Generate the first n elements of Recamán's sequence. *)
recaman[n_]:=Module[{out=ConstantArray[-1,n]},
out[[1]]=0;
Do[
If[i-1>out[[i-1]]||MemberQ[out,out[[i-1]]-i+1],
out[[i]]=out[[i-1]]+i-1,
out[[i]]=out[[i-1]]-i+1;
],
{i,2,n}];
out
]

(* Given a list of values, draws alternating over/under semicircles on the number line linking consecutive values. *)
rdraw[list_]:=Module[{g={},p=1,c,r},
(* g = list of graphics objects to display
p = parity of current list entry (±1)
c = center of new semicircle
r = radius of new semicircle *)
Do[
c=((list[[i]]+list[[i+1]])/2);
r=((Abs[list[[i]]-list[[i+1]]])/2);
g=Append[g,Circle[{c,0},r,If[p>0,{0,Pi},{Pi,2Pi}]]];
p*=-1,
{i,1,Length[list]-1}];
Graphics[g]
]

Demonstration

recaman[20]

rdraw[recaman[10]]

(* Manipulate to generate a long Recamán sequence and animate the drawing process. *)
nmax=100;
rlist=recaman[nmax];
Manipulate[Show[rdraw[rlist[[1;;n]]],PlotRange->{{-1,Max[rlist]+1},{-nmax-1,nmax+1}}],{n,2,nmax,1}]