46 lines
1.8 KiB
Text
46 lines
1.8 KiB
Text
# Let R[n] be the Recaman sequence, n >= 0, so R[0]=0.
|
|
# Input: a number, $required, specifying the required range of integers, [1 .. $required]
|
|
# to be covered by R[0] ... R[.n]
|
|
# $capture: the number of elements of the sequence to retain.
|
|
# Output: an object as described below.
|
|
# Note that .a|length will be equal to $capture.
|
|
#
|
|
def recaman_required($capture):
|
|
. as $required
|
|
| {
|
|
n: 0,
|
|
current: 0, # R[.n]
|
|
previous: null, # R[.n-1]
|
|
a: [0], # only maintained up to a[$capture-1]
|
|
used: { "0": true }, # hash for checking whether a value has already occurred
|
|
found: { "0": true }, # hash for checking how many in [0 .. $required] inclusive have been found
|
|
nfound: 1, # .found|length
|
|
foundDup: null, # the first duplicated entry in the sequence
|
|
foundDupAt: null # .foundDup == R[.foundDupAt]
|
|
}
|
|
| until ((.n >= $capture) and .foundDup and (.nfound > $required);
|
|
.n += 1
|
|
| .current -= .n
|
|
| if (.current < 1 or .used[.current|tostring]) then .current = .current + 2*.n else . end
|
|
| (.current|tostring) as $s
|
|
| .used[$s] as $alreadyUsed
|
|
| if .n < $capture then .a += [.current] else . end
|
|
| if ($alreadyUsed|not)
|
|
then .used[$s] = true
|
|
| if (.current >= 0 and .current <= $required)
|
|
then .found[$s] = true | .nfound+=1
|
|
else . end
|
|
else .
|
|
end
|
|
| if (.foundDup|not) and $alreadyUsed
|
|
then .foundDup = .current
|
|
| .foundDupAt = .n
|
|
else .
|
|
end );
|
|
|
|
1000 as $required
|
|
| 15 as $capture
|
|
| $required | recaman_required($capture)
|
|
| "The first \($capture) terms of Recaman's sequence are: \(.a)",
|
|
"The first duplicated term is a[\(.foundDupAt)] = \(.foundDup)",
|
|
"Terms up to a[\(.n)] are needed to generate 0 to \($required) inclusive."
|