|
| |
|
|
A005132
|
|
Recaman'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)
|
|
99
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| The name "Recaman's sequence" is due to N. J. A. Sloane (njas(AT)research.att.com), not the author!
I conjecture that every number eventually appears - see A057167, A064227, A064228. - N. J. A. Sloane (njas(AT)research.att.com).
Comment from David Wilson (dwilson(AT)gambitcomm.com), 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
|
|
|
REFERENCES
| N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane and A. R. 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
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
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
Tilman Piesk, First 172 items in a coordinate system
Index entries for sequences related to Recaman'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
|
|
|
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] (* From 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)) (from 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))} (from 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), A063733.
Cf. A064227 (records for reaching n), A064228 (n's that take a record number of steps to reach), A064284 (no. of times n appears), A064288, A064289, A064290 (heights of terms).
Cf. A064291 (record highs), A064387, A064388, A064389 (further variants).
A row of A066201.
Condensed version: A119632.
Cf. A079053.
Sequence in context: A065232 A074170 A076543 * A064388 A064387 A064389
Adjacent sequences: A005129 A005130 A005131 * A005133 A005134 A005135
|
|
|
KEYWORD
| easy,nonn,nice
|
|
|
AUTHOR
| B. Recaman [Recam\'{a}n], N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
|
EXTENSIONS
| Allan Wilks (allan(AT)research.att.com), Nov 06, 2001, computed 10^15 terms of this sequence. At this point the smallest missing number is 852655.
After 10^25 terms of A005132 the smallest missing number is still 852655. - Benjamin Chaffin (chaffin(AT)gmail.com), Jun 13 2006
Even after 7.78*10^37 terms, the smallest missing number is still 852655. - Benjamin Chaffin (chaffin(AT)gmail.com), Mar 28 2008
Even after 4.28*10^73 terms, the smallest missing number is still 852655. - Benjamin Chaffin (chaffin(AT)gmail.com), Mar 22 2010
|
| |
|
|
