% 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