# Recaman's sequence

N. J. A. Sloane njas at research.att.com
Sun Sep 23 10:56:32 CEST 2001

```Dear Seqfans, one of my favorite sequences is Recaman's ("subtract if you can,

%I A005132 M2511
%S A005132 1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,
%T A005132 42,17,43,16,44,15,45,14,46,79,113,78,114,77,39,78,38,79,37,80,
%U A005132 36,81,35,82,34,83,33,84,32,85,31,86,30,87,29,88,28,89,27,90,26
%N A005132 Recaman's sequence: a(n) = a(n-1)-n if positive and new, else a(n) = a(n-1)+n.
%C A005132 I conjecture that every number eventually appears - see A057167, A064227, A064228.
%D A005132 R. K. Guy and R. Nowakowski, Unsolved Problems, Amer. Math. Monthly, vol 102 (1995), circa page 924.
%H A005132 C. L. Mallows, <a href="http://www.research.att.com/~njas/sequences/a5132.jpg">Plot (jpeg) of first 10000 terms</a>
%H A005132 C. L. Mallows, <a href="http://www.research.att.com/~njas/sequences/a5132.ps">Plot (postscript) of first 10000 terms</a>
%H A005132 N. J. A. Sloane, My favorite integer sequences (<a href="http://www.research.att.com/~njas/doc/sg.pdf">pdf</a>, <A HREF="http://www.research.att.com/~njas/doc/sg.ps">ps</a>), in Sequences and their Applications (Proceedings of SETA '98), C. Ding, T. Helleseth and H. Niederreiter (editors), Springer-Verlag, London, 1999, pp. 103-130.
%H A005132 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/a005132.txt">Fortran program for A005132, A057167, A064227, A064228</a>
%e A005132 Consider n=6. We have a(5)=7 and try to subtract 6. The result, 1, is certainly positive, but we cannot use it because 1 is already in the sequence. So we must add 6 instead, getting a(6) = 7 + 6 = 13.
%p A005132 h:= array(1..100000); maxt:=100000; a:=[1]; ad:=[1]; su:=[]; h[1]:=1; for nx from 2 to 500 do t1:=a[nx-1]-nx; if t1>0 and h[t1] <> 1 then su:=[op(su),nx]; else t1:=a[nx-1]+nx; ad:=[op(ad),nx]; fi; a:=[op(a),t1]; if t1 <= maxt then h[t1]:= 1; fi; od: # a is A005132, ad is A057165, su is A057166
%Y A005132 Cf. A057165 (addition steps), A057166 (subtraction steps), A057167 (steps to hit n), A008336, A046901, A063733.
%Y A005132 Cf. A064227 (records for reaching n), A064228 (n's that take a record number of steps to reach).
%K A005132 easy,nonn,nice
%O A005132 1,2
%A A005132 B. Recaman [Recam\'{a}n], njas, sp

The big question is, does every number appear?
Here is the time for n to appear for the first time:

%I A057167
%S A057167 1,4,2,131,129,3,5,16,14,12,10,8,6,31,29,27,25,23,99734,7,9,11,13,
%T A057167 15,17,64,62,60,58,56,54,52,50,48,46,44,42,40,38,111,22,20,18,28,30,
%U A057167 32,222,220,218,216,214,212,210,208,206,204,202,200,198,196
%N A057167 Term in Recaman's sequence A005132 where n appears for first time, or 0 if n never appears.
%H A057167 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/a005132.txt">Fortran program for A005132, A057167, A064227, A064228</a>
%p A057167 w:=array(1..10000); for j from 1 to 100 do l:=0; for k from 1 to nops(a) do if a[k] = j then l:=k; exit; fi; od: w[j]:=l; od: s:=[seq(w[j],j=1..100)]; # where a is an array formed from sequence A005132
%K A057167 nonn,easy,nice
%O A057167 1,2
%A A057167 njas, Sep 14 2000
%E A057167 I conjecture a(n) is never 0 - but see A064227, A064228.

Note that 4 does not appear until the 131-st term,
and 19 does not appear until the 99734-th term!
Here are the record times and the corresponding n's:

%I A064227
%S A064227 1,4,131,99734,181653,328002
%N A064227 From Recaman's sequence (A005132): record values in A057167.
%C A064227 Is this sequence infinite?
%H A064227 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/a005132.txt">Fortran program for A005132, A057167, A064227, A064228</a>
%K A064227 nonn,nice,more,new
%O A064227 1,2
%A A064227 njas, Sep 22 2001

%I A064228
%S A064228 1,2,4,19,61,879
%N A064228 From Recaman's sequence (A005132): values of n achieving records in A057167.
%H A064228 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/a005132.txt">Fortran program for A005132, A057167, A064227, A064228</a>
%K A064228 nonn,nice,more,new
%O A064228 1,2
%A A064228 njas, Sep 22 2001

I am posting this in the hope that someone will extend the last two sequences.
I hope David Wilson is listening!  (However, email to him does not
seem to be working)

NJAS

```