

A005132


Recamán's sequence (or Recaman's sequence): a(0) = 0; for n > 0, a(n) = a(n1)  n if nonnegative and not already in the sequence, otherwise a(n) = a(n1) + n.
(Formerly M2511)


194



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. That was written in 1991. Today I'm not so sure that every number appears.  N. J. A. Sloane, Feb 26 2017
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
From David W. Wilson, Jul 13 2009: (Start)
The sequence satisfies [1] a(n) >= 0, [2] a(n)a(n1) = n, and tries to avoid repeats by greedy choice of a(n) = a(n1) + n.
This "wants" to be an injection on N = {0, 1, 2, ...}, as it attempts to avoid repeats by choice of a(n) = a(n1) + n when a(n) = a(n1)  n is a repeat.
Clearly, there are injections satisfying [1] and [2], e.g., a(n) = n(n+1)/2.
Is there a lexicographically earliest injection satisfying [1] and [2]? (End)
Answer: Yes, of course: The set of injections satisfying [1] and [2] is not empty, so there's a lexicographically least element. More concretely, it starts with the same 23 terms a(0..22) which are known to be minimal, but after a(22) = 41 it has to go on with a(23) = 41 + 23 = 64, since choosing "" here necessarily yields a noninjective sequence. See A171884.  M. F. Hasler, Apr 01 2019
It appears that a(n) is also the value of "x" and "y" of the endpoint of the Ltoothpick structure mentioned in A210606 after nth stage.  Omar E. Pol, Mar 24 2012
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
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
This sequence cycles clockwise around the OEIS icon.  Ryan Brooks, May 09 2020


REFERENCES

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.
Benjamin Chaffin, N. J. A. Sloane, and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.
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).


LINKS

N. J. A. Sloane, The first 100000 terms
Alex Bellos and Brady Haran, The Slightly Spooky Recamán Sequence, Numberphile video, 2018.
Alex Bellos and Brady Haran, Edmund Harriss's illustration of first 62 steps drawn as a spiral, 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.
Benjamin Chaffin, Loglog plot of first 10^230 terms
Benjamin Chaffin, Status Report, Jan 25 2018.
Michael De Vlieger, video of first 1200 steps of the Recamán sequence, with audio accompaniment generated by aspects of the sequence. Oct 12, 2019.
GBnums, A nice OEIS sequence
Gordon Hamilton, Wrecker Ball Sequences, Video, 2013
Edmund Harriss, The first 65 steps drawn as a spiral
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
Joseph Samuel Myers, Richard Schroeppel, Scott R. Shannon, N. J. A. Sloane, and Paul Zimmermann, Three Cousins of Recaman's Sequence, arXiv:2004:14000 [math.NT], April 2020.
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, 2012.
Omar E. Pol, Illustration of initial terms of A001057, A005132, A000217, 2012.
Bernardo Recamán Santos and N. J. A. Sloane, Correspondence, 1991.
Scott R. Shannon, Illustration of the first 2000 terms plotted as steps on a 2D square (Ulam) spiral. The colors are graduated across the spectrum from red to violet to show the relative step order.
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
Alex van den Brandhof, Een bizarre rij, Pythagoras, 55ste Jaargang, Nummer 2, Nov 2015 (Article in Dutch about this sequence, see page 19 and back cover).
Index entries for sequences related to Recamán's sequence


FORMULA

a(k) = A000217(k)  2*Sum_{i=1..n} A057166(i), for A057166(n) <= k < A057166(n+1).  Christopher Hohl, Jan 27 2019


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[nx1]nx; if t1>0 and h[t1] <> 1 then su := [op(su), nx]; else t1 := a[nx1]+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, found, j;
if n = 0 then return 0 fi;
a := procname(n1)  n ;
if a <= 0 then return a+2*n fi;
found := false;
for j from 0 to n1 while not found do
found := procname(j) = a;
od;
if found then a+2*n else a fi;
end: # R. J. Mathar, Apr 01 2012 (reformatted by Peter Luschny, Jan 06 2019)
seq(A005132(n), n=0..70);


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
(* Second program: *)
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(n1)n)1)+setsearch(Set(vector(n1, i, a(i))), a(n1)n), a(n1)+n, a(n1)n)) \\ Benoit Cloitre
(PARI) A005132(N=1000, show=0)={ my(s, t); for(n=1, N, s=bitor(s, 1<<t += if( t<=n  bittest(s, tn), n, n)); show&&print1(t", ")); t} \\ M. F. Hasler, May 11 2008, updated M. F. Hasler, Nov 03 2014
(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(n1)(n1);
C=0.^( abs(B+1) + (B+1) );
D=ismember(B, a(1:n1));
a(n)=a(n1)+ (n1) * (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 (xn) : recaman (insert (xn) s) (n+1) (xn)
else (x+n) : recaman (insert (x+n) s) (n+1) (x+n)
 Reinhard Zumkeller, Mar 14 2011
(Python)
l=[0]
for n in range(1, 101):
x=l[n  1]  n
if x>0 and not x in l: l+=[x, ]
else: l+=[l[n  1] + n]
l # Indranil Ghosh, Jun 01 2017
(Python3)
def recaman(n):
seq = []
for i in range(n):
if(i == 0): x = 0
else: x = seq[i1]i
if(x>=0 and x not in seq): seq+=[x]
else: seq+=[seq[i1]+i]
return seq
print(recaman(1000)) # Ely Golden, Jun 14 2018


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).
A065056 gives partial sums, A160356 gives first differences.
A row of A066201.
Cf. A171884 (injective variant).
See A324784, A324785, A324786 for the "low points".
Cf. A330791, A331659, A331670.
Sequence in context: A274648 A277558 A335299 * A064388 A064387 A064389
Adjacent sequences: A005129 A005130 A005131 * A005133 A005134 A005135


KEYWORD

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 all the numbers below 852655 had appeared, but 852655 = 5*31*5501 was missing.
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
Even after 10^230 terms, the smallest missing number is still 852655.  Benjamin Chaffin, 2018
Changed "positive" in definition to "nonnegative".  N. J. A. Sloane, May 04 2020


STATUS

approved



