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.


 
# Let R[n] be the Recaman sequence, n >= 0, so R[0]=0.
# Input: a number, $required, specifying the required range of integers, [1 .. $required]
#        to be covered by R[0] ... R[.n]
# $capture: the number of elements of the sequence to retain.
# Output: an object as described below.
# Note that .a|length will be equal to $capture.
#
def recaman_required($capture):
  . as $required
  | {
      n: 0,
      current: 0,                 # R[.n]
      previous: null,             # R[.n-1]
      a: [0],                     # only maintained up to a[$capture-1]
      used:  { "0": true },       # hash for checking whether a value has already occurred
      found: { "0": true },       # hash for checking how many in [0 .. $required] inclusive have been found
      nfound: 1,                  # .found|length
      foundDup: null,             # the first duplicated entry in the sequence
      foundDupAt: null            # .foundDup == R[.foundDupAt]
     }
  | until ((.n >= $capture) and .foundDup and (.nfound > $required);
      .n += 1
      | .current -= .n
      | if (.current < 1 or .used[.current|tostring]) then .current = .current + 2*.n else . end
      | (.current|tostring) as $s
      | .used[$s] as $alreadyUsed
      | if .n < $capture then .a += [.current] else . end
      | if ($alreadyUsed|not)
        then .used[$s] = true
	| if (.current >= 0 and .current <= $required)
	  then .found[$s] = true | .nfound+=1
	  else . end
        else .
	end
      | if (.foundDup|not) and $alreadyUsed
        then .foundDup = .current
	| .foundDupAt = .n
        else .
	end );
 
1000 as $required
| 15 as $capture
| $required | recaman_required($capture)
| "The first \($capture) terms of Recaman's sequence are: \(.a)",
  "The first duplicated term is a[\(.foundDupAt)] = \(.foundDup)",
  "Terms up to a[\(.n)] are needed to generate 0 to \($required) inclusive."