login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)
141

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

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

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

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

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

%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

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

%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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 26 23:21 EDT 2017. Contains 288777 sequences.