This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005132 Recamán's sequence (or Recaman's sequence): a(0) = 0; for n > 0, a(n) = a(n-1) - n if positive and not already in the sequence, otherwise a(n) = a(n-1) + n. (Formerly M2511) 144

%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 Recamán's sequence (or Recaman's sequence): a(0) = 0; for n > 0, a(n) = a(n-1) - n if positive and not already in the sequence, otherwise a(n) = a(n-1) + n.

%C The name "Recamán'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_. That was written in 1991. Today I'm not so sure that every number appears. - _N. J. A. Sloane_, Feb 26 2017

%C As of Jan 25 2018, the first 13 missing numbers are 852655, 930058, 930557, 964420, 966052, 966727, 969194, 971330, 971626, 971866, 972275, 972827, 976367, ... For further information see the "Status Report" link. - _Benjamin Chaffin_, Jan 25 2018

%C From _David W. Wilson_, Jul 13 2009: (Start)

%C 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 earliest injection satisfying [1] and [2]? (End)

%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. - _Omar E. Pol_, Mar 24 2012

%C Of course this is not a permutation of the integers: the first repeated term is 42 = a(24) = a(20). - _M. F. Hasler_, Nov 03 2014. Also 43 = a(18) = a(26). - _Jon Perry_, Nov 06 2014

%C Of all the sequences in the OEIS, this one is my favorite to listen to. Click the "listen" button at the top, set the instrument to "103. FX 7 (Echoes)", click "Save", and open the MIDI file with a program like QuickTime Player 7. - _N. J. A. Sloane_, Aug 08 2017

%D Alex Bellos and Edmund Harriss, Visions of the Universe (2016), Unnumbered pages. Includes Harriss's illustration of the first 65 steps drawn as a spiral.

%D Bernardo Recamá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 Alex Bellos and Brady Haran, <a href="https://www.youtube.com/watch?v=FGC5TdIiT9U">The Slightly Spooky Recamán Sequence</a>, Numberphile video, 2018.

%H Alex Bellos and Brady Haran, <a href="/A005132/a005132_1.png">Edmund Harriss's illustration of first 62 steps drawn as a spiral</a>, snapshot from Numberphile vidoe "The Slightly Spooky Recamán Sequence" at 2:37 minutes. [Included with permission of the authors] See also the Harriss link below.

%H Benjamin Chaffin, <a href="/A005132/a005132.png">Log-log plot of first 10^230 terms</a>

%H Benjamin Chaffin, <a href="/A005132/a005132_1.txt">Status Report</a>, Jan 25 2018

%H GBnums, <a href="http://www.echolaliste.com/gbnums/index.htm">See: A nice OEIS sequence</a>

%H Gordon Hamilton, <a href="http://www.youtube.com/watch?v=mQdNaofLqVc&amp;feature=youtu.be">Wrecker Ball Sequences</a>, Video, 2013

%H Edmund Harriss, <a href="/A005132/a005132_1.pdf">The first 65 steps drawn as a spiral</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 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polrec01.jpg">Illustration of initial terms</a>, 2012.

%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polcrt01.jpg">Illustration of initial terms of A001057, A005132, A000217</a>, 2012.

%H Bernardo Recamán Santos and N. J. A. Sloane, <a href="/A005132/a005132.pdf">Correspondence</a>, 1991.

%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 Alex van den Brandhof, <a href="http://www.pyth.eu/jaargangen/Pyth55-2.pdf">Een bizarre rij</a>, Pythagoras, 55ste Jaargang, Nummer 2, Nov 2015, (Article in Dutch about this sequence, see page 19 and back cover).

%H <a href="/index/Rea#Recaman">Index entries for sequences related to Recamán'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] (* _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)) \\ _Benoit Cloitre_

%o (PARI) A005132(N=1000,show=0)={ my(s,t); for(n=1,N, s=bitor(s,1<<t += if( t<=n || bittest(s, t-n), n, -n)); show&&print1(t","));t} \\ _M. F. Hasler_, May 11 2008, updated _M. F. Hasler_, Nov 03 2014

%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 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

%o (Python)

%o l=[0]

%o for n in xrange(1, 101):

%o x=l[n - 1] - n

%o if x>0 and not x in l: l+=[x, ]

%o else: l+=[l[n - 1] + n]

%o print l # _Indranil Ghosh_, Jun 01 2017

%o (Python3)

%o def recaman(n):

%o seq = []

%o for i in range(n):

%o if(i == 0): x = 0

%o else: x = seq[i-1]-i

%o if(x>=0 and x not in seq): seq+=[x]

%o else: seq+=[seq[i-1]+i]

%o return seq

%o print(recaman(1000)) # _Ely Golden_, Jun 14 2018

%Y Cf. A057165 (addition steps), A057166 (subtraction steps), A057167 (steps to hit n), A008336, A046901 (simplified version), A064227 (records for reaching n), A064228 (value of n that take a record number of steps to reach), A064284 (no. of times n appears), A064290 (heights of terms), A064291 (record highs), A119632 (condensed version), A063733, A079053, A064288, A064289, A064387, A064388, A064389, A228474 (bidirectional version).

%Y A065056 gives partial sums, A160356 gives first differences.

%Y A row of A066201.

%K nonn,nice,hear,look

%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 was 852655 = 5*31*5501.

%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

%E Even after 10^230 terms, the smallest missing number is still 852655. - _Benjamin Chaffin_, Mar 22 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 18 20:06 EST 2018. Contains 318245 sequences. (Running on oeis4.)