14
\$\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\$
  • 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
  • \$\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\$
3
\$\begingroup\$

05AB1E, 25 bytes

Outputs the nth item 1-indexed

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

Try it online!

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

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.