Recaman's sequence

Recaman's sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Recamán's sequence generates Natural numbers.
Starting from zero, the n'th term a(n) is the previous term minus n i.e a(n) = a(n-1) - n but only if this is both positive and has not been previousely generated.

If the conditions don't hold then a(n) = a(n-1) + n.

Task

1. Generate and show here the first 15 members of the sequence.
2. Find and show here, the first duplicated number in the sequence.
3. Optionally: Find and show here, How many terms of the sequence are needed until all the integers 0..1000, inclusive, are generated.

References

• A005132, The On-Line Encyclopedia of Integer Sequences.
• The Slightly Spooky Recamán Sequence, Numberphile video.

Python

<lang python>from itertools import islice

class Recamans():

   "Recamán's sequence generator callable class"
   def __init__(self):
       self.a = None   # Set of results so far
       self.n = None   # n'th term (counting from zero)
   
   def __call__(self):
       "Recamán's sequence  generator"
       nxt = 0
       a, n = {nxt}, 0
       self.a = a
       self.n = n
       yield nxt
       while True:
           an1, n = nxt, n + 1
           nxt = an1 - n
           if nxt < 0 or nxt in a:
               nxt = an1 + n
           a.add(nxt)
           self.n = n
           yield nxt

if __name__ == '__main__':

   recamans = Recamans()
   print("First fifteen members of Recamans sequence:", 
         list(islice(recamans(), 15)))

   so_far = set()
   for term in recamans():
       if term in so_far:
           print(f"First duplicate number in series is: a({recamans.n}) = {term}")
           break
       so_far.add(term)
   
   n = 1_000
   setn = set(range(n + 1))    # The target set of numbers to be covered
   for _ in recamans():
       if setn.issubset(recamans.a):
           print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})")
           break</lang>

Output:

First fifteen members of Recamans sequence: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
First duplicate number in series is: a(24) = 42
Range 0 ..1000 is covered by terms up to a(328002)

REXX

<lang rexx>/*REXX program computes & displays the Recaman sequence (also known as Recamán sequence)*/ parse arg N h . /*obtain optional arguments from the CL*/ if N== | N=="," then N= 15 /*Not specified? Then use the default.*/ say "Recamán's sequence for the first " N " numbers:" say recaman(N) say say "The first duplicate number in the Recamán's sequence is: " recaman(0) exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ recaman: procedure; parse arg y 1 oy,,$ !. d.; u=0 /*U: a unique flag. */

        if y==0  then do;  y=1e8;  u=1;  end                     /*for duplicate stuff.*/
        @.=0                                                     /*initialize  @  array*/
             do j=0  for y;      jm=j-1;    p=@.jm
             _=p+j
             if p<=j  then do;   @.j=_;     !._=.;    end        /*for pository values.*/
                      else do;   m=p-j
                           @.j=m                                 /*for negatory values.*/
                           if !.m==.  then do;   @.j=_;   !._=.  /*was defined before? */
                                           end
                           end
             z=@.j                                               /*get the  @.J  value.*/
             if u  then do;   if d.z==.  then return z;   d.z=.;   iterate  /*j*/;    end
             $=$  z                                              /*append  Z  to list. */
             end   /*j*/
        return strip($)                                          /*return the  $  list.*/</lang>

output   when using the default input:

Recamán's sequence for the first  15  numbers:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

The first duplicate number in the Recamán's sequence is:  42

zkl

<lang zkl>fcn recamanW{ // -->iterator -->(n,a,True if a is a dup)

  Walker.tweak(fcn(rn,rp,d){
     n,p,a := rn.value, rp.value, p - n;
     if(a<=0 or d.find(a)) a+=2*n;
     d.incV(a); rp.set(a);
     return(rn.inc(),a,d[a]>1);
  }.fp(Ref(0),Ref(0),Dictionary()) )

}</lang> <lang zkl>print("First 15 members of Recaman's sequence: "); recamanW().walk(15).apply("get",1).println();

n,a := recamanW().filter1("get",2); // ie filter(a[n].dup) println("First duplicate number in series is: a(%d) = %d".fmt(n,a));

rw,ns,n,a,dup := recamanW(),1000,0,0,0; do{ n,a,dup=rw.next(); if(not dup and a<1000) ns-=1; }while(ns); println("Range 0..1000 is covered by terms up to a(%,d)".fmt(n));</lang>

Output:

First 15 members of Recamans sequence: L(0,1,3,6,2,7,13,20,12,21,11,22,10,23,9)
First duplicate number in series is: a(24) = 42
Range 0..1000 is covered by terms up to a(328,002)