33
\$\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.

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

48 Answers 48

1
2
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}
\$\endgroup\$
1
\$\begingroup\$

PHP, 89 bytes

$f=function($n){for(;$i<$n;$s[$r[$i++]=$p=$m]=1)if($s[$m=$p-$i]|0>$m)$m=$p+$i;return$r;};

Try it online!

Ungolfed:

$f = function ($n) {
    for (; $i < $n; $s[$r[$i++] = $p = $m] = 1) {
        if ($s[$m = $p - $i] | 0 > $m) {
            $m = $p + $i;
        }
    }

    return $r;
};
  • $r for my result
  • $s for tracking seens
  • $p previous value
  • $m mext value
\$\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)))
\$\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

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

Perl 5, 65 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 36 bytes

(,][`(+2*#)@.(e.+.0>[)~{:-#)^:(]`0:)

Try it online!

\$\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!

\$\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
\$\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!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 56 52 bytes

-2 bytes thanks to Jo King!
-2 bytes thanks to dingledooper!

->n{v,*d=0;n.times{|i|d<<v+=v<i||d!=d-[v-i]?i:-i};d}

Try it online!

Commented:

->n{ ... }                         # lambda function taking an integer
  v,*d=0                           # initialize list of sequence values d and previous value v
  n.times{|i| ... }                # run the following code for i = 0,1,...,n-1:
          v<i||d!=d-[v-i]?i:-i     #   i IF (v < i OR d != (d without v-i)) ELSE -i
       v+=                         #   add this to v
    d<<                            #   and append the new value of v to d
  d                                # return d
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can remove the parenthesises by flipping the inequality. Try it online! \$\endgroup\$
    – Jo King
    Feb 11 at 4:29
  • 1
    \$\begingroup\$ You can also you splat to initialize both variables at once Try it online! \$\endgroup\$ Feb 11 at 5:25
  • \$\begingroup\$ @JoKing Thanks a lot! I didn't even realise I needed the parentheses because of the ?. \$\endgroup\$
    – ovs
    Feb 11 at 12:05
1
\$\begingroup\$

Japt, 20 bytes

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

Try it

\$\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
\$\endgroup\$
0
\$\begingroup\$

Haskell, 77 bytes

f 0=[0]
f n=let y=last x;x=f$n-1in x++[last$y-n:[y+n|y<n||y-n`elem`x]]
f.pred

Try it online!

\$\endgroup\$
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 :)

\$\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));}
\$\endgroup\$
1
  • \$\begingroup\$ Size reduced from 117 to 108 bytes by using a function template shortcut syntax. \$\endgroup\$
    – user272735
    Jul 28 '19 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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