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.


import scala.collection.mutable
 
object RecamansSequence extends App {
  val (a, used) = (mutable.ArrayBuffer[Int](0), mutable.BitSet())
  var (foundDup, hop, nUsed1000) = (false, 1, 0)
 
  while (nUsed1000 < 1000) {
    val _next = a(hop - 1) - hop
    val next = if (_next < 1 || used.contains(_next)) _next + 2 * hop else _next
    val alreadyUsed = used.contains(next)
 
    a += next
    if (!alreadyUsed) {
      used.add(next)
      if (next <= 1000) nUsed1000 += 1
    }
    if (!foundDup && alreadyUsed) {
      println(s"The first duplicate term is a($hop) = $next")
      foundDup = true
    }
    if (nUsed1000 == 1000)
      println(s"Terms up to $hop are needed to generate 0 to 1000")
 
    hop += 1
  }
 
  println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}")
 
}