17
\$\begingroup\$

Recamán's Sequence is defined as follows:

\$a_n=\begin{cases}0\quad\quad\quad\quad\text{if n = 0}\\a_{n-1}-n\quad\text{if }a_{n-1}-n>0\text{ and is not already in the sequence,}\\a_{n-1}+n\quad\text{otherwise}\end{cases}\$

or in pseudo-code:

a(0) = 0,
if (a(n - 1) - n) > 0 and it is not 
   already included in the sequence,
     a(n) = a(n - 1) - n 
else 
     a(n) = a(n - 1) + n. 

The first numbers are (OEIS A005132):

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

If you study this sequence, you'll notice that there are duplicates, for instance a(20) = a(24) = 42 (0-indexed). We'll call a number a duplicate if there is at least one identical number in front of it in the sequence.


Challenge:

Take an integer input k, and output either the first k duplicate numbers in the order they are found as duplicates in Recamán's Sequence, or only the k'th number.

This first duplicated numbers are:

42, 43, 78, 79, 153, 154, 155, 156, 157, 152, 265, 261, 262, 135, 136, 269, 453, 454, 257, 258, 259, 260, 261, 262

A few things to note:

  • a(n) does not count as a duplicate if there are no identical numbers in a(0) ... a(n-1), even if a(n+m)==a(n).
  • 42 will be before 43, since its duplicate occurs before 43's duplicate
  • The sequence is not sorted
  • There are duplicate elements in this sequence too. For instance the 12th and the 23rd numbers are both 262 (0-indexed).

Test cases (0-indexed)

k      Output
    0      42
    9     152
   12     262
   23     262
  944    5197
  945   10023
10000   62114

This is , so the shortest code in each language wins!

Explanations are encouraged!

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Related \$\endgroup\$ – ngm Jun 27 '18 at 14:04
  • \$\begingroup\$ Why isn't 43 output before 42? It appears first in Recamán's sequence. Do you mean output first the one that is first found to be a duplicate? \$\endgroup\$ – Luis Mendo Jun 27 '18 at 14:30
  • 1
    \$\begingroup\$ @LuisMendo As I understand it, \$43\$ should appear after \$42\$ because its duplicate occurrence is later on in the sequence (so the second occurrence of \$42\$ lies before the second occurrence of \$43\$). \$\endgroup\$ – Mr. Xcoder Jun 27 '18 at 14:35
  • \$\begingroup\$ I also, saw the popular math.SE question recently :P \$\endgroup\$ – orlp Jun 27 '18 at 15:11
  • 1
    \$\begingroup\$ @orlp huh? Can you link to it? I haven't seen it... \$\endgroup\$ – Stewie Griffin Jun 27 '18 at 15:20
5
\$\begingroup\$

Wolfram Language (Mathematica), 88 85 76 bytes

(For[i=k=j=p=0,k<#,i~FreeQ~p||k++,i=i|p;p+=If[p>++j&&FreeQ[i,p-j],-j,j]];p)&

Try it online!

1-indexed.

Explanation

For[

For loop.

i=k=j=p=0

Start with i (\$=\{a_1, a_2, \ldots\}\$), k (number of duplicates found), j (\$=n\$), p(\$=a_{n-1}\$) equal to 0.

k<#

Repeat while k is less than the input.

i=i|p

Append p to i using the head Alternatives (a golfier version of List in this case).

p+=If[p>++j&&FreeQ[i,p-j],-j,j]

Increment j. If p is greater than j (i.e. \$a_{n-1} > n\$) and p-j is not in i (i.e. \$a_{n-1} - n\$ is new), then increment p by -j. Otherwise, increment p by j.

i~FreeQ~p||k++

Each iteration, increment k if p is not in i (the || (= or) short-circuits otherwise).

... ;p

Return p.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 91 bytes

k=input();n=0;l=n,
while k:n+=1;x=l[-1]-n;u=x+2*n*(x<1or x in l);k-=u in l;l+=u,
print l[n]

Try it online!

1-indexed.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 78 bytes

n=input()
l=[];d=x=0
while n:d-=1;l+=x,d;x+=[d,-d][x+d in l];n-=x in l
print x

Try it online!

\$\endgroup\$
4
+100
\$\begingroup\$

APL (Dyalog Unicode), 56 54 49 48 bytes (SBCS)

Saved 2 7 bytes thanks to @ovs!

Saved 1 byte thanks to @Adám

0∘{×⍵:r,⍣d⊢(r,⍺)∇⍵-d←⍺∊⍨r←(⊃((≤∨⍺∊⍨-)⌷-,+)≢)⍺⋄⍬}

Try it online!

Can be f k. Recursively builds up the first k duplicates.

⍺ holds Recamán's sequence (in reverse), and is set to 0 if no argument is given (at the start). If k (⍵) is 0, it returns an empty array (⍬). Otherwise, it computes the next term r. If r is present in ⍺, it calls itself with r,⍺ as the left argument and ⍵-1 as the right argument, and prepends r to the result of that. If not, it just returns (r,⍺) f ⍵, hoping for the next iteration to find a duplicate.

⎕IO←0 has to be used before using this, since it relies on 0-indexing.

0∘          ⍝ Default argument to start off the sequence
{×⍵:       ⍝ If k is greater than 1:
    r←(⊃((≤∨⍺∊⍨-)⌷-,+)≢)⍺
                       ≢     ⍝ Current n is the size of ⍺.
       ⊃                     ⍝ First element of ⍺ (a_{n-1})
                 ⌷           ⍝ Index into
                   -,+       ⍝ a_{n-1} - n, a_{n-1} + n using
         (≤∨⍺∊⍨-)           ⍝ another train to return 1 or 0
          ≤                  ⍝ If a_{n-1} is not greater than n
           ∨                 ⍝ or
               -             ⍝ a_{n-1} - n
            ⍺∊⍨             ⍝ is already in a,
                            ⍝ use a+n, otherwise a-n
    d←⍺∊⍨r                        ⍝ Whether or not r (a_n) is a duplicate

  (r,⍺)∇⍵-d                        
  (r,⍺)                           ⍝ Add r to ⍺, because it's part of Recaman's sequence
        ⍵-d                       ⍝ Decrement k if r is a duplicate
       ∇                          ⍝ Call itself, find the next duplicates

  r(,⍣d)(r,⍺)∇⍵-d
     ⍣d                           ⍝ If d is 0, just return (r,⍺)∇⍵-d
  r ,                             ⍝ Otherwise, add r to the list of duplicates (which is returned from (r,⍺)∇⍵-d

⋄⍬        ⍝ If k is 0, return an empty array
}
```
\$\endgroup\$
6
  • 2
    \$\begingroup\$ You can do 0∘{...} to use 0 as a default left argument. \$\endgroup\$ – ovs Nov 27 '20 at 23:23
  • \$\begingroup\$ @ovs Oh, that's smart, thanks! \$\endgroup\$ – user Nov 27 '20 at 23:25
  • \$\begingroup\$ 49 bytes by adding more trains ;). If you don't want to change the index origin, r←(⊃(⊃(≤∨⍺∊⍨-)↓-,+)≢)⍺ works for 50 bytes. \$\endgroup\$ – ovs Nov 28 '20 at 15:11
  • \$\begingroup\$ @ovs Wow, thanks! I think I'll use the ⎕IO←0 version \$\endgroup\$ – user Nov 28 '20 at 15:44
  • \$\begingroup\$ (,⍣d),⍣d⊢ \$\endgroup\$ – Adám Dec 6 '20 at 14:03
3
\$\begingroup\$

05AB1E, 25 bytes

Outputs the nth item 1-indexed

¾ˆµ¯D¤N-DŠD0›*åN·*+©å½®Dˆ

Try it online!

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

JavaScript (ES6), 66 59 bytes

Returns the N-th term, 0-indexed.

i=>(g=x=>!g[x+=x>n&!g[x-n]?-n:n]||i--?g(g[n++,x]=x):x)(n=0)

Try it online!

How?

We use g() as our main recursive function and as an object to keep track of the duplicates.

i => (                    // given i
  g = x =>                // g = recursive function and generic object
    !g[x +=               // update x:
      x > n & !g[x - n] ? //   if x is greater than n and x - n was not visited so far:
        -n                //     subtract n from x
      :                   //   else:
        n                 //     add n to x
    ]                     // if x is not a duplicate
    || i-- ?              // or x is a duplicate but not the one we're looking for:
      g(g[n++, x] = x)    //   increment n, mark x as visited and do a recursive call
    :                     // else:
      x                   //   stop recursion and return x
)(n = 0)                  // initial call to g() with n = x = 0
\$\endgroup\$
0
2
\$\begingroup\$

Pyth, 34 33 bytes

J]0@LJ.f}K+=G-eJZ*yZ|}GJ<G0~+JKQ1

Try it online!

Outputs the n first duplicates.

*waits for Jelly or one of the new stack languages to enter*

\$\endgroup\$
0
0
\$\begingroup\$

Rust, 160 bytes

|k|{let(mut a,mut r,mut n,mut i,mut v)=(vec!(0),0,1usize,0,0);while i<k{v=if v>n&&!a.contains(&(v-n)){v-n}else{v+n};if a.contains(&v){r=v;i+=1}a.push(v);n+=1}r}

Try it online!

Ungolfed:

|k| {
  let mut a=vec!(0);
  let mut r=0;
  let mut n=1usize;
  let mut i=0;
  let mut v=r;
  while i < k {
    v = if v > n && !a.contains(&(v-n)) { 
      v - n
    } else { 
      v + n 
    };
    if a.contains(&v) {
      r = v;
      i += 1
    }
    a.push(v);
    n += 1
  }
  r
}
\$\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.