Recaman's sequence

From Rosetta Code
Task
Recaman's sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The Recamán's sequence generates Natural numbers.
Starting from zero, the n'th term a(n) 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
  1. Generate and show here the first 15 members of the sequence.
  2. Find and show here, the first duplicated number in the sequence.
  3. Optionally: Find and show here, How many terms of the sequence are needed until all the integers 0..1000, inclusive, are generated.


References



AppleScript[edit]

The third of these tasks probably stretches Applescript a bit beyond the point of its usefulness – it takes about 1 minute to find the result, and even that requires the use of NSMutableSet, from the Apple Foundation classes.

use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
 
on run
 
-- FIRST FIFTEEN RECAMANs ------------------------------------------------------
 
script term15
on |λ|(i)
15 = (i as integer)
end |λ|
end script
set strFirst15 to unwords(snd(recamanUpto(true, term15)))
 
set strFirstMsg to "First 15 Recamans:" & linefeed
display notification strFirstMsg & strFirst15
delay 2
 
-- FIRST DUPLICATE RECAMAN ----------------------------------------------------
 
script firstDuplicate
on |λ|(_, seen, rs)
setSize(seen) as integer is not (length of (rs as list))
end |λ|
end script
set strDuplicate to (item -1 of snd(recamanUpto(true, firstDuplicate))) as integer as string
 
set strDupMsg to "First duplicated Recaman:" & linefeed
display notification strDupMsg & strDuplicate
delay 2
 
-- NUMBER OF RECAMAN TERMS NEEDED TO GET ALL OF [0..1000]
-- (takes about a minute, depending on system)
 
set setK to setFromList(enumFromTo(0, 1000))
script supersetK
on |λ|(i, setR)
setK's isSubsetOfSet:(setR)
end |λ|
end script
 
display notification "Superset size result will take c. 1 min to find ..."
set dteStart to current date
 
set strSetSize to (fst(recamanUpto(false, supersetK)) - 1) as string
 
set dteEnd to current date
 
set strSetSizeMsg to "Number of Recaman terms needed to generate" & ¬
linefeed & "all integers from [0..1000]:" & linefeed
set strElapsed to "(Last result took c. " & (dteEnd - dteStart) & " seconds to find)"
display notification strSetSizeMsg & linefeed & strSetSize
 
-- CLEARED REFERENCE TO NSMUTABLESET -------------------------------------
set setK to missing value
 
-- REPORT ----------------------------------------------------------------
unlines({strFirstMsg & strFirst15, "", ¬
strDupMsg & strDuplicate, "", ¬
strSetSizeMsg & strSetSize, "", ¬
strElapsed})
end run
 
-- nextR :: Set Int -> Int -> Int
on nextR(seen, i, n)
set bk to n - i
if 0 > bk or setMember(bk, seen) then
n + i
else
bk
end if
end nextR
 
-- recamanUpto :: Bool -> (Int -> Set Int > [Int] -> Bool) -> (Int, [Int])
on recamanUpto(bln, p)
script recaman
property mp : mReturn(p)'s |λ|
on |λ|()
set i to 1
set r to 0
set rs to {r}
set seen to setFromList(rs)
repeat while not mp(i, seen, rs)
set r to nextR(seen, i, r)
setInsert(r, seen)
if bln then set end of rs to r
set i to i + 1
end repeat
set seen to missing value -- clear pointer to NSMutableSet
{i, rs}
end |λ|
end script
recaman's |λ|()
end recamanUpto
 
-- GENERIC FUNCTIONS -------------------------------------------------------
 
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
return lst
else
return {}
end if
end enumFromTo
 
-- fst :: (a, b) -> a
on fst(tpl)
if class of tpl is record then
|1| of tpl
else
item 1 of tpl
end if
end fst
 
-- intercalateS :: String -> [String] -> String
on intercalateS(sep, xs)
set {dlm, my text item delimiters} to {my text item delimiters, sep}
set s to xs as text
set my text item delimiters to dlm
return s
end intercalateS
 
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
 
-- NB All names of NSMutableSets should be set to *missing value*
-- before the script exits.
-- ( scpt files containing residual ObjC pointer values can not be saved)
-- setFromList :: Ord a => [a] -> Set a
on setFromList(xs)
set ca to current application
ca's NSMutableSet's ¬
setWithArray:(ca's NSArray's arrayWithArray:(xs))
end setFromList
 
-- setMember :: Ord a => a -> Set a -> Bool
on setMember(x, objcSet)
missing value is not (objcSet's member:(x))
end setMember
 
-- setInsert :: Ord a => a -> Set a -> Set a
on setInsert(x, objcSet)
objcSet's addObject:(x)
objcSet
end setInsert
 
-- setSize :: Set a -> Int
on setSize(objcSet)
objcSet's |count|() as integer
end setSize
 
-- snd :: (a, b) -> b
on snd(tpl)
if class of tpl is record then
|2| of tpl
else
item 2 of tpl
end if
end snd
 
-- unlines :: [String] -> String
on unlines(xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set str to xs as text
set my text item delimiters to dlm
str
end unlines
 
-- unwords :: [String] -> String
on unwords(xs)
intercalateS(space, xs)
end unwords
Output:
First 15 Recamans:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

First duplicated Recaman:
42

Number of Recaman terms needed to generate
all integers from [0..1000]:
328002

(Last result took c. 40 seconds to find)

C[edit]

Library: GLib
Translation of: Go
#include <stdio.h>
#include <stdlib.h>
#include <gmodule.h>
 
typedef int bool;
 
int main() {
int i, n, k = 0, next, *a;
bool foundDup = FALSE;
gboolean alreadyUsed;
GHashTable* used = g_hash_table_new(g_direct_hash, g_direct_equal);
GHashTable* used1000 = g_hash_table_new(g_direct_hash, g_direct_equal);
a = malloc(400000 * sizeof(int));
a[0] = 0;
g_hash_table_add(used, GINT_TO_POINTER(0));
g_hash_table_add(used1000, GINT_TO_POINTER(0));
 
for (n = 1; n <= 15 || !foundDup || k < 1001; ++n) {
next = a[n - 1] - n;
if (next < 1 || g_hash_table_contains(used, GINT_TO_POINTER(next))) {
next += 2 * n;
}
alreadyUsed = g_hash_table_contains(used, GINT_TO_POINTER(next));
a[n] = next;
 
if (!alreadyUsed) {
g_hash_table_add(used, GINT_TO_POINTER(next));
if (next >= 0 && next <= 1000) {
g_hash_table_add(used1000, GINT_TO_POINTER(next));
}
}
 
if (n == 14) {
printf("The first 15 terms of the Recaman's sequence are: ");
printf("[");
for (i = 0; i < 15; ++i) printf("%d ", a[i]);
printf("\b]\n");
}
 
if (!foundDup && alreadyUsed) {
printf("The first duplicated term is a[%d] = %d\n", n, next);
foundDup = TRUE;
}
k = g_hash_table_size(used1000);
 
if (k == 1001) {
printf("Terms up to a[%d] are needed to generate 0 to 1000\n", n);
}
}
g_hash_table_destroy(used);
g_hash_table_destroy(used1000);
free(a);
return 0;
}
Output:
The first 15 terms of the Recaman's sequence are: [0 1 3 6 2 7 13 20 12 21 11 22 10 23 9]
The first duplicated term is a[24] = 42
Terms up to a[328002] are needed to generate 0 to 1000

Go[edit]

package main
 
import "fmt"
 
func main() {
a := []int{0}
used := make(map[int]bool, 1001)
used[0] = true
used1000 := make(map[int]bool, 1001)
used1000[0] = true
for n, foundDup := 1, false; n <= 15 || !foundDup || len(used1000) < 1001; n++ {
next := a[n-1] - n
if next < 1 || used[next] {
next += 2 * n
}
alreadyUsed := used[next]
a = append(a, next)
 
if !alreadyUsed {
used[next] = true
if next >= 0 && next <= 1000 {
used1000[next] = true
}
}
 
if n == 14 {
fmt.Println("The first 15 terms of the Recaman's sequence are:", a)
}
 
if !foundDup && alreadyUsed {
fmt.Printf("The first duplicated term is a[%d] = %d\n", n, next)
foundDup = true
}
 
if len(used1000) == 1001 {
fmt.Printf("Terms up to a[%d] are needed to generate 0 to 1000\n", n)
}
}
}
Output:
The first 15 terms of the Recaman's sequence are: [0 1 3 6 2 7 13 20 12 21 11 22 10 23 9]
The first duplicated term is a[24] = 42
Terms up to a[328002] are needed to generate 0 to 1000

Haskell[edit]

Recursion[edit]

A basic recursive function for the first N terms,

import Data.List (find)
import Data.Maybe (isNothing)
 
recaman :: Int -> [Int]
recaman n = fst <$> reverse (go n)
where
go x
| 1 > x = []
| 1 == x = [(0, 1)]
| otherwise =
let xs@((r, i):_) = go (pred x)
back = r - i
in ( if 0 < back && isNothing (find ((back ==) . fst) xs)
then back
else r + i
, succ i) :
xs
 
main :: IO ()
main = print $ recaman 15
Output:
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]

Conditional iteration[edit]

Or, a little more flexibly, a recamanUpto (predicate) function.

Translation of: JavaScript
import Data.Set (Set, fromList, insert, isSubsetOf, member, size)
 
recamanUpto :: (([Int], Int, Set Int) -> Bool) -> [Int]
recamanUpto p = rs
where
(rs, _, _) =
until
p
(\(rs@(r:_), i, seen) ->
let n = nextR seen i r
in (n : rs, succ i, insert n seen))
([0], 1, fromList [0])
 
nextR :: Set Int -> Int -> Int -> Int
nextR seen i r =
let back = r - i
in if 0 > back || member back seen
then r + i
else back
 
firstNRecamans :: Int -> [Int]
firstNRecamans n = reverse $ recamanUpto (\(_, i, _) -> n == i)
 
firstDuplicateR :: Int
firstDuplicateR = head $ recamanUpto (\(rs, _, set) -> size set /= length rs)
 
recamanSuperset :: Set Int -> [Int]
recamanSuperset setInts =
tail $ recamanUpto (\(_, _, setR) -> isSubsetOf setInts setR)
 
-- TEST ---------------------------------------------------------------
main :: IO ()
main =
(putStrLn . unlines)
[ "First 15 Recamans:"
, show $ firstNRecamans 15
, []
, "First duplicated Recaman:"
, show firstDuplicateR
, []
, "Length of Recaman series required to include [0..1000]:"
, (show . length . recamanSuperset) $ fromList [0 .. 1000]
]
Output:
First 15 Recamans:
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]

First duplicated Recaman:
42

Length of Recaman series required to include [0..1000]:
328002

Lazy search over infinite lists[edit]

For a lazier solution, we could define an infinite series of Recaman sequences of growing length, starting with [0], and simply search through them for the first series of length 15, or the first to include a duplicated integer. For the third task, it would be enough to search through an infinite stream of Recaman-generated integer sets of increasing size, until we find the first that contains [0..1000] as a subset.

import Data.Set (Set, fromList, insert, isSubsetOf, member)
import Data.List (find, findIndex, nub)
import Control.Applicative (liftA2)
import Data.Maybe (fromJust)
 
-- Infinite stream of Recaman series of growing length
rSeries :: [[Int]]
rSeries =
scanl
(\rs@(r:_) i ->
(let back = r - i
in (if (0 > back) || elem back rs
then r + i
else back) :
rs))
[0]
[1 ..]
 
-- Infinite stream of Recaman-generated integer sets, of growing size
rSets :: [(Set Int, Int)]
rSets =
scanl
(\(seen, r) i ->
(let back = r - i
nxt =
if (0 > back) || member back seen
then r + i
else back
in (insert nxt seen, nxt)))
(fromList [0], 0)
[1 ..]
 
-- TEST ---------------------------------------------------------------
main :: IO ()
main = do
let setK = fromList [0 .. 1000]
(putStrLn . unlines)
[ "First 15 Recamans:"
, show . reverse . fromJust $ find ((15 ==) . length) rSeries
, []
, "First duplicated Recaman:"
, show . head . fromJust $ find (liftA2 (/=) length (length . nub)) rSeries
, []
, "Length of Recaman series required to include [0..1000]:"
, show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets
]
Output:
First 15 Recamans:
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]

First duplicated Recaman:
42

Length of Recaman series required to include [0..1000]:
328002

JavaScript[edit]

Translation of: Haskell
(() => {
const main = () => {
 
console.log(
'First 15 Recaman:\n' +
recamanUpto(i => 15 === i)
);
 
console.log(
'\n\nFirst duplicated Recaman:\n' +
last(recamanUpto(
(_, set, rs) => set.size !== rs.length
))
);
 
const setK = new Set(enumFromTo(0, 1000));
console.log(
'\n\nNumber of Recaman terms needed to generate' +
'\nall integers from [0..1000]:\n' +
(recamanUpto(
(_, setR) => isSubSetOf(setK, setR)
).length - 1)
);
};
 
// RECAMAN --------------------------------------------
 
// recamanUpto :: (Int -> Set Int > [Int] -> Bool) -> [Int]
const recamanUpto = p => {
let
i = 1,
r = 0, // First term of series
rs = [r];
const seen = new Set(rs);
while (!p(i, seen, rs)) {
r = nextR(seen, i, r);
seen.add(r);
rs.push(r);
i++;
}
return rs;
}
 
// Next Recaman number.
 
// nextR :: Set Int -> Int -> Int
const nextR = (seen, i, n) => {
const back = n - i;
return (0 > back || seen.has(back)) ? (
n + i
) : back;
};
 
// GENERIC --------------------------------------------
 
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
m <= n ? iterateUntil(
x => n <= x,
x => 1 + x,
m
) : [];
 
// isSubsetOf :: Ord a => Set a -> Set a -> Bool
const isSubSetOf = (a, b) => {
for (let x of a) {
if (!b.has(x)) return false;
}
return true;
};
 
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
const vs = [x];
let h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
 
// last :: [a] -> a
const last = xs =>
0 < xs.length ? xs.slice(-1)[0] : undefined;
 
// MAIN ------------------------------------------------
return main();
})();
Output:
First 15 Recaman:
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9

First duplicated Recaman:
42

Number of Recaman terms needed to generate
all integers from [0..1000]:
328002

Kotlin[edit]

Translation of: Go
// Version 1.2.60
 
fun main(args: Array<String>) {
val a = mutableListOf(0)
val used = mutableSetOf(0)
val used1000 = mutableSetOf(0)
var foundDup = false
var n = 1
while (n <= 15 || !foundDup || used1000.size < 1001) {
var next = a[n - 1] - n
if (next < 1 || used.contains(next)) next += 2 * n
val alreadyUsed = used.contains(next)
a.add(next)
if (!alreadyUsed) {
used.add(next)
if (next in 0..1000) used1000.add(next)
}
if (n == 14) {
println("The first 15 terms of the Recaman's sequence are: $a")
}
if (!foundDup && alreadyUsed) {
println("The first duplicated term is a[$n] = $next")
foundDup = true
}
if (used1000.size == 1001) {
println("Terms up to a[$n] are needed to generate 0 to 1000")
}
n++
}
}
Output:
The first 15 terms of the Recaman's sequence are: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
The first duplicated term is a[24] = 42
Terms up to a[328002] are needed to generate 0 to 1000

Microsoft Small Basic[edit]

Inefficency of associative array allocation in Small Basic ban to provide the optional task.

' Recaman's sequence - smallbasic - 05/08/2015
nn=15
TextWindow.WriteLine("Recaman's sequence for the first " + nn + " numbers:")
recaman()
TextWindow.WriteLine(Text.GetSubTextToEnd(recaman,2))
nn="firstdup"
recaman()
TextWindow.WriteLine("The first duplicated term is a["+n+"]="+a[n])
 
Sub recaman
a=""
b=""
dup=""
recaman=""
firstdup=""
If nn="firstdup" Then
nn=1000
firstdup="True"
EndIf
For n=0 To nn-1
ap=a[n-1]+n
If a[n-1]<=n Then
a[n]=ap 'a[n]=a[n-1]+n
b[ap]=1
Else
am=a[n-1]-n
If b[am]=1 Then
a[n]=ap 'a[n]=a[n-1]+n
b[ap]=1
Else
a[n]=am 'a[n]=a[n-1]-n
b[am]=1
EndIf
EndIf
If firstdup Then
If dup[a[n]]=1 Then
Goto exitsub
EndIf
dup[a[n]]=1
EndIf
recaman=recaman+","+a[n]
EndFor
exitsub:
EndSub
Output:
Recaman's sequence for the first 15 numbers:
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9
The first duplicated term is a[24]=42

Perl 6[edit]

Works with: Rakudo version 2018.06
my @recamans = 0, {
state %seen;
state $term;
$term++;
my $this = $^previous - $term;
$this = $previous + $term unless ($this > 0) && !%seen{$this};
%seen{$this} = True;
$this
}*;
 
put "First fifteen terms of Recaman's sequence: ", @recamans[^15];
 
say "First duplicate at term: a[{ @recamans.first({@recamans[^$_].Bag.values.max == 2})-1 }]";
 
my @seen;
my int $i = 0;
loop {
next if (my int $this = @recamans[$i++]) > 1000 or @seen[$this];
@seen[$this] = 1;
say "Range 0..1000 covered by terms up to a[{$i - 1}]" and last if ++$ == 1001;
}
Output:
First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicate at term: a[24]
Range 0..1000 covered by terms up to a[328002]

Python[edit]

from itertools import islice
 
class Recamans():
"Recamán's sequence generator callable class"
def __init__(self):
self.a = None # Set of results so far
self.n = None # n'th term (counting from zero)
 
def __call__(self):
"Recamán's sequence generator"
nxt = 0
a, n = {nxt}, 0
self.a = a
self.n = n
yield nxt
while True:
an1, n = nxt, n + 1
nxt = an1 - n
if nxt < 0 or nxt in a:
nxt = an1 + n
a.add(nxt)
self.n = n
yield nxt
 
if __name__ == '__main__':
recamans = Recamans()
print("First fifteen members of Recamans sequence:",
list(islice(recamans(), 15)))
 
so_far = set()
for term in recamans():
if term in so_far:
print(f"First duplicate number in series is: a({recamans.n}) = {term}")
break
so_far.add(term)
 
n = 1_000
setn = set(range(n + 1)) # The target set of numbers to be covered
for _ in recamans():
if setn.issubset(recamans.a):
print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})")
break
Output:
First fifteen members of Recamans sequence: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
First duplicate number in series is: a(24) = 42
Range 0 ..1000 is covered by terms up to a(328002)

REXX[edit]

version 1[edit]

Programmer's note:   the short-circuited   if   REXX statement   (lines 14 & 15):

  if z<0  then              z= _ + #
          else if !.z  then z= _ + #

could've been replaced with:

  if !.z | z<0         then z= _ + #
/*REXX pgm computes a Recamán sequence up to N; the 1st dup; # terms for a range of #'s.*/
parse arg N h . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/
if h=='' | h=="," then h= 1000 /* " " " " " " */
say "Recamán's sequence for the first " N " numbers: " recaman(N)
say; say "The first duplicate number in the Recamán's sequence is: " recaman(0)
say; say "The number of terms to complete the range 0───►"h ' is: ' recaman(-h)
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
recaman: procedure; arg y 1 oy,,d.; $=0;  !.=0;  !.0=1; _=0 /*init. array and vars.*/
u=(y=0); r=(y<0); hi=abs(oy); if oy<1 then y=1e8 /*for 2nd & 3rd invoke.*/
s=0 /*# of Recamán #s found*/
do #=1 for y-1; z= _ - # /*next # might be < 0. */
if z<0 then z= _ + # /*this is faster than: */
else if !.z then z= _ + # /*if !.z | z<0 then ···*/
_=z;  !.z=1 /*add to seq; mark it.*/
if oy>0 then $=$ z /*add number to $ list?*/
if r then do; if z>hi then iterate # /*ignore #'s too large.*/
if d.z=='' then s= s + 1 /*This number unique ? */
d.z=. /*mark # as a new low #*/
if s>=hi then return # /*list is complete ≤ HI*/
end /* [↑] a range of #s. */
if u then do; if d.z==. then return z; d.z=.; end /*check if duplicate #.*/
end /*#*/
return $ /*return the $ list. */
output   when using the default input:
Recamán's sequence for the first  15  numbers:  0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

The first duplicate number in the Recamán's sequence is:  42

The number of terms to complete the range  0───►1000  is:  328002

version 2[edit]

/*REXX program computes & displays the Recaman sequence           */
/*improved using version 1's method for task 3 */
Call time 'R' /* Start timer */
Parse Arg n
If n='' Then n=15
Say 'the first' n 'elements:' recaman(n)
Say ans.2
Say ans.3
Say time('E') 'seconds elapsed'
Exit
 
recaman:
Parse Arg n /* Wanted number of elements */
have.=0 /* Number not yet in sequence */
e.0=0 /* First element */
have.0=1 /* is in the sequence */
s=0 /* Sequence to be shodn */
done=0 /* turn on first duplicate switch */
d.=0
d.0=1
dn=1 /* number of elements <=1000 */
Do i=1 until dn==1001 /* Loop until all found */
ip=i-1 /* previous index */
temp=e.ip-i /* potential next element */
If temp>0 & have.temp=0 Then /* to be used */
Nop
Else /* compute the alternative */
temp=e.ip+i
e.i=temp /* Set next element */
If words(s)<n Then /* not enough in output */
s=s temp /* add the element to the output */
If temp<=1000 Then Do /* eligible for task 3 */
If d.temp=0 Then Do /* not yet encountered */
d.temp=1 /* Remember it's there */
dn=dn+1 /* count of integers<=1000 found */
End
End
If done=0 & have.temp=1 Then Do
ans.2='First duplicate ('temp') added in iteration' i,
'elapsed:' time('E') 'seconds'
done=1
End
ans.3='Element number' i 'is the last to satisfy task 3. It is' temp
Have.temp=1
End
Return s
Output:
the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicate (42) added in iteration 24 elapsed: 0 seconds
Element number 328002 is the last to satisfy task 3. It is 879
7.126000 seconds elapsed

Sidef[edit]

func recamans_generator() {
 
var term = 0
var prev = 0
var seen = Hash()
 
{
var this = (prev - term)
 
if ((this <= 0) || seen{this}) {
this = (prev + term)
}
 
prev = this
seen{this} = true
term++
this
}
}
 
with (recamans_generator()) { |r|
say ("First 15 terms of the Recaman's sequence: ", 15.of { r.run }.join(', '))
}
 
with (recamans_generator()) {|r|
var seen = Hash()
Inf.times {|i|
var n = r.run
if (seen{n}) {
say "First duplicate term in the series is a(#{i}) = #{n}"
break
}
seen{n} = true
}
}
 
with (recamans_generator()) {|r|
var seen = Hash()
Inf.times {|i|
var n = r.run
if ((n <= 1000) && (seen{n} := true) && (seen.len == 1001)) {
say "Terms up to a(#{i}) are needed to generate 0 to 1000"
break
}
}
}
Output:
First 15 terms of the Recaman's sequence: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9
First duplicate term in the series is a(24) = 42
Terms up to a(328002) are needed to generate 0 to 1000

zkl[edit]

fcn recamanW{  // -->iterator -->(n,a,True if a is a dup)
Walker.tweak(fcn(rn,rp,d){
n,p,a := rn.value, rp.value, p - n;
if(a<=0 or d.find(a)) a+=2*n;
d.incV(a); rp.set(a);
return(rn.inc(),a,d[a]>1);
}.fp(Ref(0),Ref(0),Dictionary()) )
}
print("First 15 members of Recaman's sequence: ");
recamanW().walk(15).apply("get",1).println();
 
n,a := recamanW().filter1("get",2); // ie filter(a[n].dup)
println("First duplicate number in series is: a(%d) = %d".fmt(n,a));
 
rw,ns,n,a,dup := recamanW(),1000,0,0,0;
do{ n,a,dup=rw.next(); if(not dup and a<1000) ns-=1; }while(ns);
println("Range 0..1000 is covered by terms up to a(%,d)".fmt(n));
Output:
First 15 members of Recamans sequence: L(0,1,3,6,2,7,13,20,12,21,11,22,10,23,9)
First duplicate number in series is: a(24) = 42
Range 0..1000 is covered by terms up to a(328,002)