34
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ What does 'is new' mean? \$\endgroup\$
    – Beta Decay
    Sep 11, 2014 at 16:53
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – James Williams
    Sep 11, 2014 at 16:56
  • \$\begingroup\$ Corrected the sequence. \$\endgroup\$
    – James Williams
    Sep 11, 2014 at 17:06
  • 1
    \$\begingroup\$ Can you add the first values of the sequence? \$\endgroup\$
    – proud haskeller
    Sep 11, 2014 at 17:15
  • \$\begingroup\$ Added the first few numbers! (And a link to its OEIS page) \$\endgroup\$
    – James Williams
    Sep 11, 2014 at 17:50

49 Answers 49

Reset to default
1
2
1
\$\begingroup\$

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;}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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;
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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! \$\endgroup\$
    – Doorknob
    Aug 17, 2015 at 16:00
  • \$\begingroup\$ Sure thing, I'll do that. \$\endgroup\$
    – Abhay Jain
    Aug 18, 2015 at 17:41
1
\$\begingroup\$

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}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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)))
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 65 bytes

push@a,($t=$a[-1]-$_)+($t<0||grep$t==$_,@a)*$_*2for 0..<>;say"@a"

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 20 bytes

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

Try it

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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:
 ç  -   last Link (Link 1) as a dyad
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 77 73 bytes

f 0=[0]
f n|x<-g n,y<-last x=x++[last$y-n:[y+n|y<n||y-n`elem`x]]
g=f.pred

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 81 bytes. Recursion is probably even shorter. \$\endgroup\$
    – naffetS
    Jan 1 at 14:35
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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;}

Uses a function template shortcut syntax.

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));}
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Size reduced from 117 to 108 bytes by using a function template shortcut syntax. \$\endgroup\$
    – user272735
    Jul 28, 2019 at 8:55
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 34 bytes (Changed 0 to ⍬ to match the challenge more closely) \$\endgroup\$
    – ovs
    Jul 14, 2021 at 14:42
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.