%I A005132 M2511
%S A005132 0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42,17,
%T A005132 43,16,44,15,45,14,46,79,113,78,114,77,39,78,38,79,37,80,36,81,35,82,34,
%U A005132 83,33,84,32,85,31,86,30,87,29,88,28,89,27,90,26,91,157,224,156,225,155
%N A005132 Recaman's sequence: a(0) = 0; for n > 0, a(n) = a(n-1)-n if that number 
               is positive and not already in the sequence, otherwise a(n) = a(n-1)+n.
%C A005132 The name "Recaman's sequence" is due to N. J. A. Sloane (njas(AT)research.att.com), 
               not the author!
%C A005132 I conjecture that every number eventually appears - see A057167, A064227, 
               A064228. - N. J. A. Sloane (njas(AT)research.att.com).
%C A005132 Comment from David Wilson (dwilson(AT)gambitcomm.com), Jul 13 2009: (Start) 
               The sequence satisfies [1] a(n) >= 0, [2] |a(n)-a(n-1)| = n, and 
               tries to avoid repeats by greedy choice of a(n) = a(n-1) -+ n.
%C A005132 This "wants" to be an injection on N = {0, 1, 2, ...}, as it attempts 
               to avoid repeats by choice of a(n) = a(n-1) + n when a(n) = a(n-1) 
               - n is a repeat.
%C A005132 Clearly, there are injections satisfying [1] and [2], e.g, a(n) = n(n+1)/
               2.
%C A005132 Is there a lexicographically smallest injection satisfying [1] and [2]? 
               (End)
%D A005132 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005132 N. J. A. Sloane and A. R. Wilks, On sequences of Recaman type, paper 
               in preparation, 2006.
%H A005132 N. J. A. Sloane, <a href="b005132.txt">The first 100000 terms</a>
%H A005132 GBnums, <a href="http://www.echolaliste.com/gbnums/index.htm">See: A 
               nice OEIS sequence</a>
%H A005132 Nick Hobson, <a href="a005132.py.txt">Python program for this sequence</
               a>
%H A005132 C. L. Mallows, <a href="a5132.jpg">Plot (jpeg) of first 10000 terms</
               a>
%H A005132 C. L. Mallows, <a href="a5132.ps">Plot (postscript) of first 10000 terms</
               a>
%H A005132 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/sg.txt">
               My favorite integer sequences</a>, in Sequences and their Applications 
               (Proceedings of SETA '98).
%H A005132 N. J. A. Sloane, <a href="a005132.txt">FORTRAN program for A005132, A057167, 
               A064227, A064228</a>
%H A005132 <a href="Sindx_Rea.html#Recaman">Index entries for sequences related 
               to Recaman's sequence</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
%t A005132 a = {1}; Do[ If[ a[ [ -1 ] ] - n > 0 && Position[ a, a[ [ -1 ] ] - n 
               ] == {}, a = Append[ a, a[ [ -1 ] ] - n ], a = Append[ a, a[ [ -1 
               ] ] + n ] ], {n, 2, 70} ]; a
%t A005132 f[s_List] := Block[{a = s[[ -1]], len = Length@s}, Append[s, If[a > len 
               && !MemberQ[s, a - len], a - len, a + len]]]; Nest[f, {0}, 70] [From 
               Robert G. Wilson v (rgwv(AT)rgwv.com), May 01 2009]
%o A005132 (PARI) a(n)=if(n<2,1,if(abs(sign(a(n-1)-n)-1)+setsearch(Set(vector(n-1,
               i,a(i))),a(n-1)-n),a(n-1)+n,a(n-1)-n)) (from Benoit Cloitre)
%o A005132 A005132( nMax=10^3 )={ local( s, t ); for( n=1,nMax, print1( t += if( 
               t<=n | bittest( s, t-n ), n, -n), ","); s=bitor( s, 1<<t))} (from 
               M. F. Hasler, May 11 2008)
%Y A005132 Cf. A057165 (addition steps), A057166 (subtraction steps), A057167 (steps 
               to hit n), A008336, A046901 (simplified version), A063733.
%Y A005132 Cf. A064227 (records for reaching n), A064228 (n's that take a record 
               number of steps to reach), A064284 (no. of times n appears), A064288, 
               A064289, A064290 (heights of terms).
%Y A005132 Cf. A064291 (record highs), A064387, A064388, A064389 (further variants).
%Y A005132 A row of A066201.
%Y A005132 Condensed version: A119632.
%Y A005132 Sequence in context: A065232 A074170 A076543 this_sequence A064388 A064387 
               A064389
%Y A005132 Adjacent sequences: A005129 A005130 A005131 this_sequence A005133 A005134 
               A005135
%K A005132 easy,nonn,nice
%O A005132 0,3
%A A005132 B. Recaman [Recam\'{a}n], N. J. A. Sloane (njas(AT)research.att.com), 
               Simon Plouffe (simon.plouffe(AT)gmail.com)
%E A005132 Allan Wilks (allan(AT)research.att.com), Nov 06, 2001, computed 10^15 
               terms of this sequence. At this point the smallest missing number 
               is 852655.
%E A005132 After 10^25 terms of A005132 the smallest missing number is still 852655. 
               - Benjamin Chaffin (chaffin(AT)gmail.com), Jun 13 2006
%E A005132 Even after 7.78*10^37 terms, the smallest missing number is still 852655. 
               - Benjamin Chaffin (chaffin(AT)gmail.com), Mar 28 2008