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.


 
visited <- vector('logical', 1e8)
 
terms <- vector('numeric')
 
in_a_interval <- function(v) {
	visited[[v+1]] 
}
 
add_value <- function(v) {
	visited[[v+1]] <<- TRUE
	terms <<- append(terms, v)
}
 
add_value(0)
step <- 1
value <- 0
 
founddup <- FALSE
 
repeat {
	if ((value-step>0) && (!in_a_interval(value-step))) {
		value <- value - step
	} else {
		value <- value + step
	}
	if (in_a_interval(value) && !founddup) {
		cat("The first duplicated term is a[",step,"] = ",value,"\n", sep = "")
		founddup <- TRUE
	}
	add_value(value)
	if (all(visited[1:1000])) {
		cat("Terms up to a[",step,"] are needed to generate 0 to 1000\n",sep = "")
		break
	}
	step <- step + 1
	if (step == 15) { 
		cat("The first 15 terms are :")
		for (aterm in terms) { cat(aterm," ", sep = "") }
		cat("\n")
	}
}
 