# Recamán's duplicates

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!

• Related – ngm Jun 27 '18 at 14:04
• 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? – Luis Mendo Jun 27 '18 at 14:30
• @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$). – Mr. Xcoder Jun 27 '18 at 14:35
• I also, saw the popular math.SE question recently :P – orlp Jun 27 '18 at 15:11
• @orlp huh? Can you link to it? I haven't seen it... – Stewie Griffin Jun 27 '18 at 15:20

# Wolfram Language (Mathematica), 8885 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.

# 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.

# 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!

# APL (Dyalog Unicode), 565449 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
}
$$$$

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

# 05AB1E, 25 bytes

Outputs the nth item 1-indexed

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


Try it online!

# 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


# 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*

# 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
}
`