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: 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.
(Formerly M2511)
127
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, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157, 224, 156, 225, 155 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The name "Recamán's sequence" is due to N. J. A. Sloane, not the author!

I conjecture that every number eventually appears - see A057167, A064227, A064228. - N. J. A. Sloane

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.

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.

Clearly, there are injections satisfying [1] and [2], e.g., a(n) = n(n+1)/2.

Is there a lexicographically smallest injection satisfying [1] and [2]? (End)

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

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

The first 14 terms appear in the logo OEIS. - Philippe Deléham, Mar 01 2013

REFERENCES

Bernardo Recamán Santos, letter to N. J. A. Sloane, Jan 29 1991

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.

LINKS

N. J. A. Sloane, The first 100000 terms

GBnums, See: A nice OEIS sequence

Gordon Hamilton, Wrecker Ball Sequences, Video, 2013

Nick Hobson, Python program for this sequence

C. L. Mallows, Plot (jpeg) of first 10000 terms

C. L. Mallows, Plot (postscript) of first 10000 terms

Tilman Piesk, First 172 items in a coordinate system [This is a graph of the start of A005132 rotated clockwise by 90 degs. - N. J. A. Sloane, Mar 23 2012]

Omar E. Pol, Illustration of initial terms

Omar E. Pol, Illustration of initial terms of A001057, A005132, A000217

N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

N. J. A. Sloane, FORTRAN program for A005132, A057167, A064227, A064228

Index entries for sequences related to Recamán's sequence

EXAMPLE

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.

MAPLE

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

A005132 := proc(n)

        option remember;

        local a, fou, j ;

        if n = 0 then 0;

        else

                a := procname(n-1)-n ;

                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;

                end if;

        end if;

end proc: # R. J. Mathar, Apr 01 2012

MATHEMATICA

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

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

PROG

(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

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))} \\ M. F. Hasler, May 11 2008

(MATLAB)

function a=A005132(m)

% m=max number of terms in a(n). Offset n:0

a=zeros(1, m);

for n=2:m

    B=a(n-1)-(n-1);

    C=0.^( abs(B+1) + (B+1) );

    D=ismember(B, a(1:n-1));

    a(n)=a(n-1)+ (n-1) * (-1)^(C + D -1);

end

% Adriano Caroli, Dec 26 2010

(Haskell)

import Data.Set (Set, singleton, notMember, insert)

a005132 n = a005132_list !! n

a005132_list = 0 : recaman (singleton 0) 1 0 where

   recaman :: Set Integer -> Integer -> Integer -> [Integer]

   recaman s n x = if x > n && (x - n) `notMember` s

                      then (x-n) : recaman (insert (x-n) s) (n+1) (x-n)

                      else (x+n) : recaman (insert (x+n) s) (n+1) (x+n)

-- Reinhard Zumkeller, Mar 14 2011

CROSSREFS

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

A row of A066201.

Sequence in context: A065232 A074170 A076543 * A064388 A064387 A064389

Adjacent sequences:  A005129 A005130 A005131 * A005133 A005134 A005135

KEYWORD

easy,nonn,nice,hear,look

AUTHOR

N. J. A. Sloane and Simon Plouffe, May 16 1991

EXTENSIONS

Allan Wilks, Nov 06 2001, computed 10^15 terms of this sequence. At this point the smallest missing number was 852655.

After 10^25 terms of A005132 the smallest missing number is still 852655. - Benjamin Chaffin, Jun 13 2006

Even after 7.78*10^37 terms, the smallest missing number is still 852655. - Benjamin Chaffin, Mar 28 2008

Even after 4.28*10^73 terms, the smallest missing number is still 852655. - Benjamin Chaffin, Mar 22 2010

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 25 19:24 EDT 2014. Contains 248557 sequences.