The Recamán's sequence generates Natural numbers.

Starting from a(0)=0, the n'th term a(n), where n>0, 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

 Generate and show here the first 15 members of the sequence.
 Find and show here, the first duplicated number in the sequence.
 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.
 Recamán's sequence, on Wikipedia.


use Collection.Generic;
 
class RecamanSequence {
  function : Main(args : String[]) ~ Nil {
    GenerateSequence();
  }
 
  function : native : GenerateSequence() ~ Nil {
    a := Vector->New()<IntHolder>;
    a->AddBack(0);
 
    used := Set->New()<IntHolder>;
    used->Insert(0);
 
    used1000 := Set->New()<IntHolder>;
    used1000->Insert(0);
 
    foundDup := false;
    n := 1;
    while (n <= 15 | <>foundDup | used1000->Size() < 1001) {
      next := a->Get(n - 1) - n;
      if (next < 1 | used->Has(next)) {
        next += 2 * n;
      };
      alreadyUsed := used->Has(next);
      a->AddBack(next);
      if (<>alreadyUsed) {
        used->Insert(next);
        if (0 <= next & next <= 1000) {
          used1000->Insert(next);
        };
      };
      if (n = 14) {
        str := ToString(a);
        "The first 15 terms of the Recaman sequence are : {$str}"->PrintLine();
      };
      if (<>foundDup & alreadyUsed) {
        "The first duplicate term is a[{$n}] := {$next}"->PrintLine();
        foundDup := true;
      };
      if (used1000->Size() = 1001) {
        "Terms up to a[{$n}] are needed to generate 0 to 1000"->PrintLine();
      };
      n++;
    };
  }
 
  function : ToString(a : Vector<IntHolder>) ~ String {
    out := "[";
    each(i : a) {
      out += a->Get(i)->Get();
      if(i + 1 < a->Size())  {
        out += ',';
      };
    };
    out += ']';
 
    return out;
  }
}