A005132 Recamán's sequence (or Recaman's sequence): a(0) = 0; for n > 0, a(n) = a(n-1) - n if nonnegative and not already in the sequence, otherwise a(n) = a(n-1) + n.
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
Offset: 0
Examples
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.
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
- Farid Aliniaeifard and Shu Xiao Li, Peak algebra in noncommuting variables, arXiv:2506.12868 [math.CO], 2025. See p. 45.
- 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 video "The Slightly Spooky Recamán Sequence" (2018) at 2:37 minutes. [Included with permission of the authors] See also the Harriss link below.
- Harlan Brothers, Recamán's Blues (a sonification Recamán's sequence), Animation, Jun 8, 2024.
- Benjamin Chaffin, Log-log plot of first 10^230 terms
- Benjamin Chaffin, Status Report, Jan 25 2018.
- Fabio Deelan Cunden, Marilena Ligabò, and Tommaso Monni, Random matrices associated to Young diagrams, arXiv:2301.13555 [math.PR], 2023. See p. 7.
- 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
- Bradley Klee, Code for pdf spiral drawing (golang)
- Bradley Klee, The first 65 steps drawn as a spiral (color)
- Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
- 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 of A001057, A005132, A000217, 2012.
- Omar E. Pol, Illustration of initial terms, 2012.
- Omar E. Pol, Lateral view of a 3D-model whose front view is formed by spirals, 2022 (using Plot 2 A005132 vs A000004)
- 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.
- Muhammad Khubab Siddique, Sequence and Series-I, Unit 8, Mathematics-II, Dept. of Sci. Ed., Allama Iqbal Open Univ. (Islamabad, Pakistan, 2020), 281-313.
- 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
- N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, pp. 10, 12-13.
- 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
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.
Cf. A171884 (injective variant).
Programs
-
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 -
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
-
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, found, j; if n = 0 then return 0 fi; a := procname(n-1) - n ; if a <= 0 then return a+2*n fi; found := false; for j from 0 to n-1 while not found do found := procname(j) = a; od; if found then a+2*n else a fi; end: seq(A005132(n), n=0..70); # R. J. Mathar, Apr 01 2012 (reformatted by Peter Luschny, Jan 06 2019)
-
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 *) RecamanSeq[i_Integer] := Fold[With[{lst=Last@#, len=Length@#}, Append[#, If[lst > len && !MemberQ[#, lst - len], lst - len, lst + len]]] &, {0}, Range@i]; RecamanSeq[10^5] (* Mikk Heidemaa, Nov 02 2024 *) -
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
-
PARI
A005132(N=1000,show=0)={ my(s,t); for(n=1,N, s=bitor(s,1<
M. F. Hasler, May 11 2008, updated M. F. Hasler, Nov 03 2014 -
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] print(l) # Indranil Ghosh, Jun 01 2017 -
Python
def recaman(n): seq = [] for i in range(n): if(i == 0): x = 0 else: x = seq[i-1]-i if(x>=0 and x not in seq): seq+=[x] else: seq+=[seq[i-1]+i] return seq print(recaman(1000)) # Ely Golden, Jun 14 2018 -
Python
from itertools import count, islice def A005132_gen(): # generator of terms a, aset = 0, set() for n in count(1): yield a aset.add(a) a = b if (b:=a-n)>=0 and b not in aset else a+n A005132_list = list(islice(A005132_gen(),30)) # Chai Wah Wu, Sep 15 2022
Formula
a(k) = A000217(k) - 2*Sum_{i=1..n} A057166(i), for A057166(n) <= k < A057166(n+1). - Christopher Hohl, Jan 27 2019
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
Comments