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

pretty latex

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

31 Answers 31

9
\$\begingroup\$

CJam, 34 33 bytes

0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`

Try it online.

Example run

$ cjam <(echo '0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`') <<< 33
[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]

How it works

0ali                               " Push S := [ 0 ] and read an integer N from STDIN.    ";
    {                      }fI     " For each I in [ 0 ... (N - 1) ]:                     ";
     _W=                           "   X := S[-1].                                        ";
        _I-                        "   Y := X - I                                         ";
            _0<                    "   A := (Y < 0)                                       ";
           _   4$@#)               "   B := (Y ∊ S)                                       ";
                     @I+           "   Z := X + I                                         ";
                    |   @?         "   C := (A || B) ? Z : Y                              ";
                          +        "   S += [C]                                           ";
                              1>`  " Push str(S[1:]).                                     ";
\$\endgroup\$
  • \$\begingroup\$ What change did you make? \$\endgroup\$ – Soham Chowdhury Sep 11 '14 at 19:55
  • \$\begingroup\$ My first approach prepended negative numbers to the sequence, so I didn't have to explicitly check if A(i) - i > 0. However, I didn't prepend enough numbers for small values of n. Now, I just do exactly what the spec says. \$\endgroup\$ – Dennis Sep 11 '14 at 19:58
  • \$\begingroup\$ 33 vs. 45. So close and yet so far. :) \$\endgroup\$ – Ingo Bürk Sep 12 '14 at 21:07
  • \$\begingroup\$ Wow, comment without e# in Cjam... tasty cherry. \$\endgroup\$ – Chromium Jun 21 '18 at 8:04
8
\$\begingroup\$

Haskell, 74

l=0:0#1
a§v|a<0||a`elem`r v=v|1<2=0-v
a#b=a+(a-b)§b:l!!b#(b+1)
r=(`take`l)

Example usage:

λ> r 20
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62]
\$\endgroup\$
6
\$\begingroup\$

Ruby, 71 70 bytes

f=->n{a=[0];(n-1).times{|i|a+=[[b=a[-1]-i-1]-a!=[]&&b>0?b:b+2*i+2]};a}

A very "word-for-word" implementation of the definition.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 78 75 73 69 Bytes

Kudos to xnor and flornquake
Now almost 10 bytes shorter than the initial answer

m=p,=0,
exec"p+=1;k=m[-1]-p;m+=k+2*p*(k*(k>0)in m),;"*input()
print m
\$\endgroup\$
  • \$\begingroup\$ You can shorten [k,k+2*p][bool] to k+2*p*(bool). \$\endgroup\$ – xnor Sep 11 '14 at 19:04
  • \$\begingroup\$ @xnor Thanks, saved 3 Bytes. \$\endgroup\$ – Markuz Sep 11 '14 at 19:16
  • \$\begingroup\$ Also, k in m or k<0 can be k*(k>=0)in m since if k<0, the product is 0, which is in m. \$\endgroup\$ – xnor Sep 11 '14 at 19:22
  • \$\begingroup\$ @xnor Brilliant! Thanks again \$\endgroup\$ – Markuz Sep 11 '14 at 19:36
  • \$\begingroup\$ You can write -1 instead of p-1. Edit: You can also make m a tuple and write m=0, and m+=k+2*p*(k*(k>0)in m),. \$\endgroup\$ – flornquake Sep 12 '14 at 13:14
3
\$\begingroup\$

JavaScript - 81 80 79 70

Kudos to edc65 for helping me save 9 bytes

f=n=>{for(a=[x=i=0];++i<n;)a[i]=x+=x>i&a.indexOf(x-i)<0?-i:i;return a}
\$\endgroup\$
  • \$\begingroup\$ -9 :g=n=>{for(a=[x=i=0];++i<n;)a[i]=x+=x>i&a.indexOf(x-i)<0?-i:i;return a} \$\endgroup\$ – edc65 Sep 11 '14 at 18:48
  • \$\begingroup\$ @edc65 Grazie mille :) \$\endgroup\$ – William Barbosa Sep 11 '14 at 19:22
3
\$\begingroup\$

JavaScript, ES6, 74 69 characters

Run the below code in latest Firefox's Web Console.

G=n=>(i=>{for(r=[t=0];++i<n;)r[i]=t+=i>t|~r.indexOf(t-i)?i:-i})(0)||r

Will try to golf it more later.

Example usage:

G(11) -> 0,1,3,6,2,7,13,20,12,21,11
\$\endgroup\$
3
\$\begingroup\$

Golfscript (41 45)

Try it online here:

(,1,\{:~1$=~)-:^1<\.^?)!!@|^\{~)2*+}*+}/

Explanation

This is for the original 45 bytes solution, but it's still pretty much the same:

(,              # push array [0 .. n-1]
[0]\            # push sequence elements as [0] and reverse stack
{               # foreach element in [0 .. n-1] do:
  :m;           # store current element in m and discard
  .m=           # get the previous sequence element
  m)-:^         # subtract the current index from it and store in ^
  0>            # is that number greater than 0?
  \.^?)!        # is that number new to our sequence?
  @&            # logically and both checks
  {^}           # if true, push ^
  {^m)2*+}      # otherwise, add the index twice and push
  if
  +             # add new element to our sequence
}/
`               # make output pretty

Edit #1: Thanks to Dennis for shaving off 4 bytes.

\$\endgroup\$
3
\$\begingroup\$

dc, 46 bytes

sn[z+z+d0r:a]sF0[pz-d1>Fd;a0<Fddd:azln!<M]dsMx

Try it online!

This program takes input from an otherwise empty stack and outputs to stdout (newline delimited).

I'm really proud of this one - it's beating everything that isn't a dedicated golfing language, and showcases three of my favorite dc golfing tricks:

  • Stack size used as an index variable
  • Refactoring "if A then B else C" into "unconditionally C, and if A then D" where C and D combine to make B
  • the little-used random access array feature to solve a uniqueness constraint

Explanation

sn             Stores the input in register n
[z+z+0r:a]sF   Defines the macro F, which: 
    z+z+         adds twice the stack size/index variable
    0r:a         resets the "uniqueness" flag to 0 in the array a
               In context, F is the "D" in my description above, 
               changing A(z-1)-z to A(z-1)+z
0              The main loop starts with the previous sequence member on top of 
               the stack and total stack depth equal to the next index. 
               Pushing a zero accomplishes both of these things.
[              Start of the main loop M
  p               Print the previous sequence member, with newline (no pop)
  z-             Calculate A(z-1)-z
  d1>F           If that's nonpositive, (F)ix it to be A(z-1)+z
  d;a            a is my array of flags to see if we've hit this value before
  0<F            If we have, (F)ix it! (nonzero = flag, since ;a is zero by
                 default, and also zero if we just (F)ixed and therefore 
                 don't care about uniqueness right now)
  ddd            Make one copy to keep and two to eat
  :a             Flag this entry as "used" in the uniqueness array a
  zln!<M         If our "index variable" is n or less, repeat!
]dsMx          End of main loop - store it and execute
\$\endgroup\$
  • \$\begingroup\$ that's wild, i had no idea dc even existed \$\endgroup\$ – don bright Dec 31 '18 at 7:08
2
\$\begingroup\$

Java, 144

int[]f(int n){int[]a=new int[n];a[0]=0;int i,j,k,m;for(i=0;i<n-1;){k=a[i++]-i;m=0;for(j=0;j<i;)if(k==a[j++])m=1;a[i]=m<1&k>0?k:k+2*i;}return a;}
\$\endgroup\$
2
\$\begingroup\$

Lua - 141 135 139 135

function s(n)a,b={1},{[0]=0}for i=1,n do k=b[i-1]-i c=k+i+i if(k>0)and(a[k]==nil)then b[i],a[k]=k,1 else b[i],a[c]=c,1 end end return b end

readable version:

function s(n)
a,b={1},{[0]=0}
for i=1,n do 
   k=b[i-1]-i 
   c=k+i+i
   if (k>0) and (a[k]==nil) then 
      b[i],a[k]=k,1 
   else 
      b[i],a[c]=c,1
   end 
end 
return b 
end

I use 2 tables, the first one is called a and it is built so that a[i]=1 iff i has already appeared in the sequence, nil otherwise, while the second table actually holds the sequence

\$\endgroup\$
  • \$\begingroup\$ Your sequence should start with 0, though \$\endgroup\$ – William Barbosa Sep 11 '14 at 18:06
  • 1
    \$\begingroup\$ You're right, I didn't look at the question very carefully and assumed it had the same definition at mathworld (starting with 1), I think that won't cost any more character, I'll test and correct it later, I'm writing from my phone now! \$\endgroup\$ – user25169 Sep 11 '14 at 19:26
2
\$\begingroup\$

Python, 73

def f(x,t=0):
 if x:t=f(x-1);t+=2*x*(t*(t>0)in map(f,range(x)))
 return t

Edit 1: Thanks to @xnor's tips on the other Python answer! (I just realised that both look very similar.)

Edit 2: Thanks again, @xnor.

\$\endgroup\$
  • \$\begingroup\$ This gives an infinite loop. You need some sort of control flow so that f(x) doesn't always immediately call f(x-1). \$\endgroup\$ – xnor Sep 11 '14 at 19:25
  • \$\begingroup\$ @xnor fixed the code. \$\endgroup\$ – Soham Chowdhury Sep 11 '14 at 19:36
  • 1
    \$\begingroup\$ This seems to return the nth term, not the first n terms. \$\endgroup\$ – Dennis Sep 11 '14 at 19:55
  • \$\begingroup\$ Some minor saves: t=0 can go as an optional parameter to f, and t=t+ can be t+=. \$\endgroup\$ – xnor Sep 11 '14 at 20:21
2
\$\begingroup\$

MATLAB, 83 78 Bytes

Save the below as f.m (73 Bytes)

A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end

Run from command window (5 bytes)

n=9;f

If the above is not legal, then it requires 90 bytes.

function A=f(n) 
A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end
\$\endgroup\$
2
\$\begingroup\$

R: 96 characters

Golfed:

A=function(s,n,m,i){if(m==n){return(s)}else{t=i-m;if(t%in%s||t<0){t=i+m};s=c(s,t);A(s,n,m+1,t)}}

Ungolfed:

A = function(s,n,m,i) {
    if(m==n){return(s)}
    else{
        t=i-m
        if(t%in%s||t<0){t=i+m}
        s=c(s,t)
        A(s,n,m+1,t)
    }
}

Sample Run:

> An(0,34,1)
[1]   0   1   3   6   2   7  13  20  12  21  11  22  10  23   9  24   8
[18]  25  43  62  42  63  41  18  42  17  43  16  44  15  45  14  46  79
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 63 bytes

n=>(g=y=>n-x?g(a[++x]=a.includes(z=y-x)|z<0?+y+x:z):a)(a=[x=0])

Try it online

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 62 57 bytes

{(0,{$-@+@*2*($!>@||$-@∈@)given @[*-1]}...*)[^$]}

{(0,{($!=@_[*-1])+@_-@_*2*($!>@_&&$!-@_∉@_)}...*)[^$_]}

-5 bytes thanks to Jo King

Try it online!

\$\endgroup\$
  • \$\begingroup\$ that's amazing... that literally looks like my cat walked across my keyboard. \$\endgroup\$ – don bright Dec 31 '18 at 7:10
1
\$\begingroup\$

Powershell (103)

$n=Read-Host;$a=@(0);$n-=1;1..$n|%{$x=$a[-1]-$_;if($x-gt0-and!($a-like$x)){$a+=$x}else{$a+=$x+2*$_}};$a

Another 'word-for-word' implementation down here as well. Surprisingly readable for PowerShell, too.

Sequence is stored in the array $a, and printed out one term per line.

For $n=20 if we run the statement $a-join"," we get

0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62
\$\endgroup\$
1
\$\begingroup\$

Groovy : 122 118 111 chars

Golfed:

m=args[0] as int
a=[0]
(1..m-1).each{n->b=a[n-1];x=b-n;(x>0&!(x in a))?a[n]=x:(a[n]=b+n)}
a.each{print "$it "}

Ungolfed:

m = args[0] as int
a = [0]
(1..m-1).each { n->
    b = a[n-1]
    x = b-n
    ( x>0 & !(x in a) ) ? a[n] = x : (a[n] = b+n) 
}
a.each{print "$it "}

Sample Run:

bash$ groovy Rec.groovy 14
0 1 3 6 2 7 13 20 12 21 11 22 10 23
\$\endgroup\$
1
\$\begingroup\$

Clojure : 174 chars

Golfed:

(defn f[m a](let[n(count a)b(last a)x(- b n)y(if(and(> x 0)(not(.contains a x)))x(+ b n))](if(= m n)a(f m(conj a y)))))(println(f(read-string(first *command-line-args*))[0]))

Ungolfed:

(defn f[m a]
  (let [n (count a) 
        b (last a) 
        x (- b n) 
        y (if (and (> x 0) (not (.contains a x))) x (+ b n)) ]
    (if (= m n) a (f m (conj a y))) ) )

(println (f (read-string (first *command-line-args*)) [0]) )

Sample run:

bash$ java -jar clojure-1.6.0.jar rec.clj 14 
[0 1 3 6 2 7 13 20 12 21 11 22 10 23]
\$\endgroup\$
1
\$\begingroup\$

Mathcad, 54 "bytes"

enter image description here


From user perspective, Mathcad is effectively a 2D whiteboard, with expressions evaluated from left-to-right,top-to-bottom. Mathcad does not support a conventional "text" input, but instead makes use of a combination of text and special keys / toolbar / menu items to insert an expression, text, plot or component. For example, type ":" to enter the definition operator (shown on screen as ":=") or "ctl-shft-#" to enter the for loop operator (inclusive of placeholders for the iteration variable, iteration values and one body expression). What you see in the image above is exactly what appears on the user interface and as "typed" in.

For golfing purposes, the "byte" count is the equivalent number of keyboard operations required to enter an expression.

\$\endgroup\$
  • \$\begingroup\$ That's all well and good, but what are the actual keystrokes? \$\endgroup\$ – Jo King Jun 18 '18 at 13:14
1
\$\begingroup\$

C (gcc), 116 111 109 bytes

*f(n){int*a=calloc(4,n),i=0,j,k,m;for(;~i+n;a[i]=k+(m|k<1)*2*i)for(k=a[i++]-i,m=0,j=i;j--;)m=k-a[j]?m:1;n=a;}

Try it online!

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

Stax, 19 bytes

É╖C8½ΔL▄░▬L+≡ΩSa⌂¼╧

Run and debug it

Unpacked, ungolfed, and commented, it looks like this. It keeps the sequence so far on the stack, and remembers A(n - 1) in the X register. The iteration index is used for n. The first time through, it's 0, but in that iteration it generates the 0 without any special cases, so there's no need to adjust for the off-by-1 index.

0X      push 0 to main stack and store it in X register, which will store A(n - 1)
z       push an empty array that will be used to store the sequence
,D      pop input from input stack, execute the rest of the program that many times
  xi-Y  push (x-register - iteration-index) and store it in the Y register
        this is (A(n - 1) - n)
  0>    test if (A(n - 1) - n) is greater than 0 (a)
  ny#   count number of times (A(n - 1) - n) occurs in the sequence so far (b)
  >     test if (a) > (b)
    y   (A(n - 1) - n)
    xi+ A(n - 1) + n
  ?     if/else;  choose between the two values based on the condition
  X     store the result in the X register
  Q     print without popping
  +     append to sequence array

Run and debug this one

\$\endgroup\$
  • \$\begingroup\$ interesting. how does this work? \$\endgroup\$ – don bright Dec 31 '18 at 7:28
  • 1
    \$\begingroup\$ @donbright: Added some annotations and explanation. \$\endgroup\$ – recursive Jan 2 at 21:07
1
\$\begingroup\$

05AB1E, 19 bytes

¾ˆG¯¤N-DŠD0›*åN·*+ˆ

Try it online!

Explanation

¾ˆ                    # Initialize the global list with 0
  G                   # for N in [1, input-1] do:
   ¯                  # push the global list
    ¤N-               # subtract N from the last item in the list
       D              # duplicate
        Š             # move the copy down 2 spots on the stack
         D            # duplicate again
          0›          # check if it is positive
            *         # multiply, turning negative results to zero
             å        # is the result already present in the list?
              N·*     # multiply by N*2
                 +    # add to the result
                  ˆ   # add this to the list
\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – lirtosiast Jan 26 at 22:39
  • \$\begingroup\$ @lirtosiast: Been a while since I did this challenge, so this is the best explanation I can do on short notice. Hope it's enough. \$\endgroup\$ – Emigna Jan 27 at 15:53
0
\$\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;}
\$\endgroup\$
0
\$\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;
\$\endgroup\$
  • \$\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 '15 at 16:00
  • \$\begingroup\$ Sure thing, I'll do that. \$\endgroup\$ – Abhay Jain Aug 18 '15 at 17:41
0
\$\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\$
0
\$\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\$
0
\$\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\$
0
\$\begingroup\$

Tcl, 104 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\$
0
\$\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\$
0
\$\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\$

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.