Recamán's Sequence

Author

Eric W. Weisstein
October 27, 2003

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/RecamansSequence.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RecamansSequence.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additive

Recaman's sequence: a(n) = a(n-1)-n if positive and new, else a(n) = a(n-1)+n.

RecamanAdditiveList[n_]:=Rest@Nest[With[{w=Last[#]-Length[#]},
Append[#,If[w>0&&FreeQ[#,w],w,Last[#]+Length[#]]]]&,{0},
n]
RecamanAdditive[n_]:=Last@RecamanAdditiveList[n]

Table[Recaman[n],{n,20}]

Recaman[n_]:=Rest@Nest[With[{w=Last[#]-Length[#]},
Append[#,If[w>0&&FreeQ[#,w],w,Last[#]+Length[#]]]]&,{0},
n]

rec=Recaman[10000];

Plots

Show[PixelPerfect[BasePlot[Recaman/@Range[256]],BlockSize->2]]

Show[GraphicsArray[
ListPlot[RecamanAdditiveList[1000],Joined->#,DisplayFunction->Identity,
AxesLabel->TraditionalForm/@{n,a[n]},
PlotStyle->Red]&/@{True,False}]
]

pos=Flatten[Table[Position[rec,i,1],{i,10}]/.{}:>0];

LargestTerms[pos]

Clear[Recaman];

Table[Recaman[i],{i,1000}];//Timing

Recaman3[1000];//Timing

Recaman1[1] = 1;
Recaman1[n_] := Recaman1[n] = Recaman1[n-1] + 
n If[Recaman1[n-1]-n>0 && Position[Table[Recaman1[k],{k,n-1}],Recaman1[n-1]-n]=={},-1,1]

Recaman2[1]:=1
Recaman2[n_]:=Recaman[n]=Module[{f=a[n-1]-n,i},
If[f>0&&!MemberQ[Table[a[i],{i,n-1}],f],
f,
a[n-1]+n
]
]

Recaman::over= "Value `1` exceeds maximum array size permitted `2`";

Recaman3[n_,max_:10^5]:=Module[
{
used=Array[False&,max],
a=Array[0&,n],
i,f,g
},
used[[1]]=True;
a[[1]]=1;
Do[
f=If[(g=a[[i-1]]-i)>0&&used[[g]],
g,
a[[i-1]]+i
];
If[f>max,Message[Recaman::over,g,max];Break[]];
used[[f]]=True;
a[[i]]=f,
{i,2,n}
];
a
]

Multiplicative

RecamanMultiplicativeList[n_]:=Nest[With[{w=Last[#]/Length[#]},
Append[#,If[IntegerQ[w],w,Last[#]Length[#]]]]&,{1},
n]
RecamanMultiplicative[n_]:=Last@RecamanMultiplicativeList[n]

RecamanMultiplicativeList[15]