|
%I M2511
%S 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,
%T 17,43,16,44,15,45,14,46,79,113,78,114,77,39,78,38,79,37,80,36,81,35,
%U 82,34,83,33,84,32,85,31,86,30,87,29,88,28,89,27,90,26,91,157,224,156,225,155
%N 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 The name "Recaman's sequence" is due to _N. J. A. Sloane_, not the author!
%C I conjecture that every number eventually appears - see A057167, A064227, A064228. - _N. J. A. Sloane_.
%C Comment from _David W. Wilson_, 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 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 Clearly, there are injections satisfying [1] and [2], e.g, a(n) = n(n+1)/2.
%C Is there a lexicographically smallest injection satisfying [1] and [2]? (End)
%C The definition can be written as a(n) = a(n-1) -n*(-1)^(c(n)+d(n)) where c(n) and d(n) are two flags defined via b(n) = a(n-1)-n; theta(n) = 1 if n>0, =0 if n<=0; c(n) = theta(1+b(n)); d(n) = theta( product_{j=0..n-1}( a(j)-b(n))^2 ). - Adriano Caroli, Dec 26 2010
%C It appears that a(n) is also the value of "x" and "y" of the endpoint of the L-toothpick structure mentioned in A210606 after n-th stage. Note that each L-toothpick can be replaced by a semicircumference. - Omar E. Pol, Mar 24 2012
%C The first 14 terms appear in the logo OEIS. - Philippe Deléham, Mar 01 2013
%D Bernardo Recaman [Recam\'{a}n] Santos, Letter to _N. J. A. Sloane_, Jan 29 1991
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D N. J. A. Sloane and _Allan Wilks_, On sequences of Recaman type, paper in preparation, 2006.
%H N. J. A. Sloane, <a href="/A005132/b005132.txt">The first 100000 terms</a>
%H GBnums, <a href="http://www.echolaliste.com/gbnums/index.htm">See: A nice OEIS sequence</a>
%H Nick Hobson, <a href="/A005132/a005132.py.txt">Python program for this sequence</a>
%H C. L. Mallows, <a href="/A005132/a005132.jpg">Plot (jpeg) of first 10000 terms</a>
%H C. L. Mallows, <a href="/A005132/a005132.ps">Plot (postscript) of first 10000 terms</a>
%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:Recaman%27s_sequence.svg">First 172 items in a coordinate system</a> [This is a graph of the start of A005132 rotated clockwise by 90 degs. - _N. J. A. Sloane_, Mar 23 2012]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polrec01.jpg">Illustration of initial terms</a>
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polcrt01.jpg">Illustration of initial terms of A001057, A005132, A000217</a>
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).
%H N. J. A. Sloane, <a href="/A005132/a005132.txt">FORTRAN program for A005132, A057167, A064227, A064228</a>
%H <a href="/index/Rea#Recaman">Index entries for sequences related to Recaman's sequence</a>
%e 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 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
%p A005132 := proc(n)
%p option remember;
%p local a,fou,j ;
%p if n = 0 then 0;
%p else
%p a := procname(n-1)-n ;
%p if a <= 0 then return a+2*n ; else fou := false; for j from 0 to n-1 do if procname(j) = a then fou :=true; break; end if; end do; if fou then a+2*n; else a ; end if;
%p end if;
%p end if;
%p end proc: # _R. J. Mathar_, Apr 01 2012
%t 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 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, May 01 2009 *)
%o (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( 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)
%o (MATLAB)
%o function a=A005132(m)
%o % m=max number of terms in a(n). Offset n:0
%o a=zeros(1,m);
%o for n=2:m
%o B=a(n-1)-(n-1);
%o C=0.^( abs(B+1) + (B+1) );
%o D=ismember(B,a(1:n-1));
%o a(n)=a(n-1)+ (n-1) * (-1)^(C + D -1);
%o end
%o % Adriano Caroli, Dec 26 2010
%o (Haskell)
%o import Data.Set (Set, singleton, notMember, insert)
%o a005132 n = a005132_list !! n
%o a005132_list = 0 : recaman (singleton 0) 1 0 where
%o recaman :: Set Integer -> Integer -> Integer -> [Integer]
%o recaman s n x = if x > n && (x - n) `notMember` s
%o then (x-n) : recaman (insert (x-n) s) (n+1) (x-n)
%o else (x+n) : recaman (insert (x+n) s) (n+1) (x+n)
%o -- _Reinhard Zumkeller_, Mar 14 2011
%Y Cf. A057165 (addition steps), A057166 (subtraction steps), A057167 (steps to hit n), A008336, A046901 (simplified version), A063733.
%Y 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 Cf. A064291 (record highs), A064387, A064388, A064389 (further variants).
%Y A row of A066201.
%Y Condensed version: A119632.
%Y Cf. A079053.
%K easy,nonn,nice
%O 0,3
%A _N. J. A. Sloane_ and _Simon Plouffe_, May 16 1991
%E __Allan Wilks__, Nov 06, 2001, computed 10^15 terms of this sequence. At this point the smallest missing number is 852655.
%E After 10^25 terms of A005132 the smallest missing number is still 852655. - _Benjamin Chaffin_, Jun 13 2006
%E Even after 7.78*10^37 terms, the smallest missing number is still 852655. - _Benjamin Chaffin_, Mar 28 2008
%E Even after 4.28*10^73 terms, the smallest missing number is still 852655. - _Benjamin Chaffin_, Mar 22 2010
|
