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.


% Recaman sequence
recaman = cluster is new, fetch
    rep = array[int]
 
    new = proc () returns (cvt)
        a: rep := rep$predict(0,1000000)
        rep$addh(a,0)
        return(a)
    end new
 
    % Find the N'th element of the Recaman sequence
    fetch = proc (a: cvt, n: int) returns (int)
        if n > rep$high(a) then extend(a,n) end
        return(a[n])
    end fetch
 
    % See if N has already been generated
    prev = proc (a: rep, n: int) returns (bool)
        for el: int in rep$elements(a) do
            if el = n then return(true) end
        end
        return(false)
    end prev
 
    % Generate members of the sequence until 'top' is reached
    extend = proc (a: rep, top: int)
        while rep$high(a) < top do
            n: int := rep$high(a) + 1
            sub: int := a[n-1] - n
            add: int := a[n-1] + n
            if sub>0 cand ~prev(a, sub)
                then rep$addh(a, sub)
                else rep$addh(a, add)
            end
        end
    end extend
end recaman
 
 
start_up = proc () 
    po: stream := stream$primary_output()
    A: recaman := recaman$new()
 
    % Print the first 15 members
    stream$puts(po, "First 15 items:")
    for i: int in int$from_to(0, 14) do
        stream$puts(po, " " || int$unparse(A[i]))
    end
 
    % Find the first duplicated number
    begin
        i: int := 0
        while true do
            i := i + 1
            for j: int in int$from_to(0, i-1) do
                if A[i]=A[j] then exit found(i, A[i]) end
            end
        end
    end except when found(i, n: int):
        stream$putl(po, "\nFirst duplicated number: A("
                      || int$unparse(i) || ") = " || int$unparse(n))
    end
 
    % Find the amount of terms needed to generate all integers 0..1000
    begin
        seen: array[bool] := array[bool]$fill(0,1001,false)
        left: int := 1001
        n: int := -1
        while left > 0 do
            n := n + 1
            if A[n] <= 1000 cand ~seen[A[n]] then
                left := left - 1
                seen[A[n]] := true
            end
        end
        stream$putl(po, "Terms needed to generate [0..1000]: "
                     || int$unparse(n))
    end        
end start_up