80 lines
2.2 KiB
Plaintext
80 lines
2.2 KiB
Plaintext
% 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
|