# Generate Recamán's sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such:

A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n


A pretty LaTex version of the above (might be more readable):

$$A(n) = \begin{cases}0 & \textrm{if } n = 0 \\ A(n-1) - n & \textrm{if } A(n-1) - n \textrm{ is positive and not already in the sequence} \\ % Seems more readable than %A(n-1) - n & \textrm{if } A(n-1) > n \wedge \not\exists m < n: A(m) = A(n-1)-n \\ A(n-1) + n & \textrm{otherwise} \end{cases}$$

The first few terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11

To clarify, is new means whether the number is already in the sequence.

Given an integer n, via function argument or STDIN, return the first n terms of the Recamán sequence.

This is a code-golf challenge, so shortest code wins.

• What does 'is new' mean? Commented Sep 11, 2014 at 16:53
• If a number is new, it means it is not yet in the sequence. Just realized I have typed out the sequence wrong, give me a min to correct it. Commented Sep 11, 2014 at 16:56
• Corrected the sequence. Commented Sep 11, 2014 at 17:06
• Can you add the first values of the sequence? Commented Sep 11, 2014 at 17:15
• Added the first few numbers! (And a link to its OEIS page) Commented Sep 11, 2014 at 17:50

f 0=[0]
f n|x<-g n,y<-last x=x++[last$y-n:[y+n|y<n||y-nelemx]] g=f.pred  Try it online! # C#: 140 characters int i,w,t,y;int[]F(int n){var r=new int[n--];for(;i<n;y=0){w=r[i++]-i;for(t=0;y<i&&t<1;)t=w==r[y++]?1:0;r[i]=w>0&&t<1?w:r[i-1]+i;}return r;}  # C++: 180 characters (158 without cin and cout statements) int a[5000000][2]={0},i,k,l;a[0][0]=0;a[0][1]=1;cin>>k;for(i=1;i<=k;i++){l=a[i-1][0];if(l-i>0&&a[l-i][1]!=1){ a[i][0]=l-i;a[l-i][1]=1;}else{ a[i][0]=l+i;a[l+i][1]=1;}cout<<a[i][0]<<endl;  • Welcome to Programming Puzzles & Code Golf Stack Exchange! Please edit the character/byte count of your solution into your header, as shown in the other answers here. Also, please golf your code (ex. remove whitespace to reduce the character count) as much as possible. Thanks! Commented Aug 17, 2015 at 16:00 • Sure thing, I'll do that. Commented Aug 18, 2015 at 17:41 # Mathematica - 81 bytes Fold[#~Append~(#[[-1]]+If[#[[-1]]>#2&&FreeQ[#,#[[-1]]-#2],-#2,#2])&,{0},Range@#]&  ## Usage Fold[#~Append~(#[[-1]]+If[#[[-1]]>#2&&FreeQ[#,#[[-1]]-#2],-#2,#2])&,{0},Range@#]&[30] {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}  ## Common LISP (139 bytes) (defun r(n)(do*(s(i 0(1+ i))(a 0(car s))(b 0(- a i)))((> i n)(nreverse s))(push(cond((= 0 i)0)((and(> b 0)(not(find b s)))b)(t(+ a i)))s)))  Ungolfed: (defun recaman (n) (do* (series ; starts as empty list (i 0 (1+ i)) ; index variable (last 0 (car s)) ; last number in the series (low 0 (- last i))) ((> i n) ; exit condition (nreverse series)) ; return value (push ; loop body (cond ((= 0 i) 0) ; first pass ((and (> low 0) (not (find low s))) low) (t (+ last i))) series)))  # Rust, 154 139 bytes This is pretty big, but I like that it only uses one comparison per iteration instead of the 2 given, thanks to Saturating Subtraction generating a 0 if a[n-1]-n would be less than 0; and since 0 is already the first element, every would-be negative is saturated to 0 and is detected instead by the 'A already contains' comparison. Also... the size is not bad compared to Clojure, C#, C++, Common Lisp, lua.. fn r(n:usize)->Vec<usize>{let mut a=vec![0usize;n];for i in 1..n{a[i]=if a.contains(&(a[i-1].saturating_sub(i))){a[i-1]+i}else{a[i-1]-i}}a}  ungolfed fn r(n:usize)->Vec<usize>{ let mut a=vec![0usize;n]; for i in 1..n { a[i] = if a.contains(&(a[i-1].saturating_sub(i))) {a[i-1]+i} else {a[i-1]-i} }a}  Try it on the rust playground # Common Lisp, 122 bytes (setf h(make-hash-table)n(read)j 0)(dotimes(i n)(when(or(<(decf j i)0)#1=(gethash j h))(incf j(+ i i)))(print(setf #1#j)))  Try it online! The sequence is generated by from 0, the values are stored in a hash table. Here is the ungolfed version: (setf h (make-hash-table) ; create a hash table to store the results n (read) ; read the input in n j 0) ; initial value of the sequence (dotimes (i n) ; loop for i from 0 below n (when (or (< (decf j i) 0) ; the new value is the old - i; if negative (gethash j h)) ; or if the value has been already generated (incf j (+ i i))) ; set j to A(n-1) + i (third case) (print (setf (gethash j h) j))) ; store the result in the table and print it  # F#, 117 116 bytes fun n->Seq.fold(fun(l:'a list)h->let a=l.[h-1]in if a-h>0&&not(Seq.contains(a-h)l)then l@[a-h]else l@[a+h])[0][1..n]  # Perl 5, 65 bytes push@a,($t=$a[-1]-$_)+($t<0||grep$t==$_,@a)*$_*2for 0..<>;say"@a"


Try it online!

# Pyth, 24 bytes

tu+G-eG_W|g0J-eGH}JGHQ]0


Try it online!

tu+G-eG_W|g0J-eGH}JGHQ]0   Implicit: Q=eval(input())
u                   Q     Reduce [0-Q)...
]0   ... with initial value G=[0], next value as H:
eG             Last value of G (sequence so far)
-  H            Take H from the above
J                Store in J
g0J                0 >= J
}JG         Is J in G?
|                   Logical OR of two previous results
_W           H        If the above is true, negate H, otherwise leave as positive
-eG                      Subtract the above from last value in G
+G                         Append the above to G
The result of the reduction is the sequence with an extra leading 0
t                          Remove a leading 0, implicit print


# JavaScript (ES6), 57 bytes

n=>(g=k=>n--?[p+=p<k|g[p-k]?k:-k,...g(g[p]=k+1)]:[])(p=0)


Try it online!

# 05AB1E, 16 bytes

0λ£Nλ₁N-Dd*åi+ë-


Try it online.

Explanation:

 λ              # Create a recursive environment
0               # which starts at a(0)=0
£             # to output the first (implicit) input amount of values
# (which will be output implicitly in the end)
# and in each iteration, we calculate the next a(n) with:
₁          #  Push a(n-1)
N-        #  Subtract the current n
D       #  Duplicate this a(n-1)-n
d      #  Check that it's non-negative (>= 0)
*     #  Multiply it to a(n-1)-n (so it'll become 0 if it's negative)
λ      åi   #  If it's in the list of previous [a(0), ..., a(n-1)] values:
N         +  #   Add n to the implicit a(n-1)
ë   #  Else:
N         -  #   Subtract n from the implicit a(n-1) instead


# Tcl, 103 bytes

proc A n {lappend L [expr {$n?[set x [lindex [set L [A [expr$n-1]]] e]]>$n&$x-$n ni$L?$x-$n:$x+$n:0}]}


Try it online!

# Japt, 20 bytes

@TwXµY *!ZøX ªX+YÑ}h


Try it

# Jelly, 15 bytes

_Ṫ»0ḟ⁸ȯ+Ṫ⁸;
Ḷç/


A monadic Link that accepts a positive integer, $$\n\$$, and yields a list of non-negative integers, the first $$\n\$$ terms of $$\A\$$.

Try it online!

### How?

_Ṫ»0ḟ⁸ȯ+Ṫ⁸; - Link 1, next prefix of Recamán: list, current_prefix; integer, next_n
(1st call is actually made with current_prefix=0)
_           - (current_prefix) subtract (next_n)  -> [A(0)-n...,A(n-1)-n] (or A(0)-n when current_prefix=0)
Ṫ          - tail                                -> A(n-1)-n
»0        - maximum of that and zero            -> 0 or A(n-1)-n
ḟ⁸      - filter discard if in current_prefix -> [] or [A(n-1)-n]
+    - (current_prefix) add (next_n)       -> [A(0)+n...,A(n-1)+n] (or A(0)+n when current_prefix=0)
ȯ     - (filtered) logical OR (added)       -> [A(n-1)-n] or [...,A(n-1)+n] (or A(0)+n when current_prefix=0)
Ṫ   - tail                                -> A(n-1)-n or A(n-1)+n
⁸; - concatenate this to the current_prefix

Ḷç/ - Main Link: positive integer, n
Ḷ   - lowered range -> [0,1,2,...,n-1]
/ - reduce using:


# Julia 1.0, 110 81 bytes

[]|>v->0|>a->0:parse(Int,readline()).|>i->(println(a+=2(a-i in v)i-i);v=[v;a;~i])


Try it online!

-29 thx to Steffan!

• 81 bytes. Recursion is probably even shorter. Commented Jan 1, 2023 at 14:35

## Clojure, 107 bytes

#(loop[s[0]i 1](if(= i %)s(recur(conj s(let[l(last s)N(- l i)](if(or(< N 0)((set s)N))(+ l i)N)))(inc i))))


Not many tricks here, ((set s)N) evaluates to N if it is in the set and nil otherwise :)

# D, 108 bytes

T[]r(T)(T n){T[]a=[0];T[T]b;foreach(i;1..n+1){T x=a[$-1];x+=(x>i)&&!((x-i)in b)?-i:i;a~=x;b[x]=1;}return a;}  Try it online by pasting the following snippet to https://run.dlang.io/ T[]r(T)(T n){T[]a=[0];T[T]b;foreach(i;1..n+1){T x=a[$-1];x+=(x>i)&&!((x-i)in b)?-i:i;a~=x;b[x]=1;}return a;}
void main(){import std.stdio;writeln(r(10));}

• Size reduced from 117 to 108 bytes by using a function template shortcut syntax. Commented Jul 28, 2019 at 8:55

# APL (Dyalog Unicode), 40 bytesSBCS

{⌽{⍵,⍨(((∊∘⍵∨≤∘0)r)×2×≢⍵)+r←(⊃-≢)⍵}⍣⍵⊢0}


Try it online! I will be back for some more golfing and to write an explanation, just give me some hours. Ok I need some more time, in golfing this I managed to make it longer.

• 34 bytes (Changed 0 to ⍬ to match the challenge more closely)
– ovs
Commented Jul 14, 2021 at 14:42