Recaman's sequence: Difference between revisions
Content deleted Content added
m typo |
|||
(39 intermediate revisions by 19 users not shown) | |||
Line 1:
{{task}}
The '''[[wp:Recamán's sequence|Recamán's sequence]]''' generates Natural numbers.
Starting from a(0)=0, the n'th term <code>a(n)</code>, where n>0, is the previous term minus <code>n</code> i.e <code>a(n) = a(n-1) - n</code> but only if this is '''both''' positive ''and'' has not been previously generated.<br>
If the conditions ''don't'' hold then <code>a(n) = a(n-1) + n</code>.
;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,
Line 14 ⟶ 16:
* [https://oeis.org/A005132 A005132], The On-Line Encyclopedia of Integer Sequences.
* [https://www.youtube.com/watch?v=FGC5TdIiT9U The Slightly Spooky Recamán Sequence], Numberphile video.
* [https://en.wikipedia.org/wiki/Recam%C3%A1n%27s_sequence Recamán's sequence], on Wikipedia.
<br><br>
Line 19 ⟶ 22:
{{trans|Python}}
<
‘The successor for a given Recaman term,
given the set of Recaman terms seen so far.’
Line 48 ⟶ 51:
print("First duplicated Recaman:\n "recamanUntil((seen, n, r, blnNew) -> !blnNew).last)
V setK = Set(enumFromTo(0)(1000))
print("Number of Recaman terms needed to generate all integers from [0..1000]:\n "(recamanUntil((seen, n, r, blnNew) -> (blnNew & r < 1001 & :setK.is_subset(seen))).len - 1))</
{{out}}
Line 61 ⟶ 64:
=={{header|ALGOL W}}==
<
% calculate Recaman's sequence values %
Line 75 ⟶ 78:
reference(AValue) array hashTable ( 0 :: HMOD - 1 );
integer array A ( 0 :: 14 );
integer le1000Count, firstN, duplicateN, duplicateValue, n, An, An1, prevN, maxS;
% adds an element to the hash table, returns true if an element with value An %
Line 104 ⟶ 107:
A( 0 ) := An1 := n := 0;
le1000Count := 0;
maxS := firstN := duplicateN := duplicateValue := -1;
while le1000Count < 1000 do begin
logical le0, duplicate;
Line 127 ⟶ 130:
else if An <= 1000 then le1000Count := le1000Count + 1;;
if n < 15 then A( n ) := An;
if An > maxS then maxS := An;
An1 := An
end while_le1000Count_lt_1000 ;
Line 145 ⟶ 149:
);
% number of elements required to include the first 1000 integers %
write( i_w := 1, "first element to include all 1..1000: ", n );
write( i_w := 1, "max sequence value encountered: ", maxS )
end
end.</
{{out}}
<pre>
Line 154 ⟶ 159:
First duplicates: 20 24 (42)
first element to include all 1..1000: 328002
max sequence value encountered: 1942300
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<
genNext←{
R←⍵[N-1]-N←≢⍵
Line 170 ⟶ 176:
⎕←'Length of sequence containing [0..1000]:'
⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca
}</
{{out}}
Line 185 ⟶ 191:
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 framework "Foundation"
use scripting additions
Line 372 ⟶ 378:
on unwords(xs)
intercalateS(space, xs)
end unwords</
{{Out}}
<pre>First 15 Recamans:
Line 385 ⟶ 391:
(Last result took c. 40 seconds to find)</pre>
=={{header|Arturo}}==
{{trans|Python}}
<syntaxhighlight lang="rebol">recamanSucc: function [seen, n, r].memoize[
back: r - n
(or? 0 > back contains? seen back)? -> n + r
-> back
]
recamanUntil: function [p][
n: new 1
r: 0
rs: new @[r]
seen: rs
blnNew: true
while [not? do p][
r: recamanSucc seen n r
blnNew: not? in? r seen
seen: unique seen ++ r
'rs ++ r
inc 'n
]
return rs
]
print "First 15 Recaman numbers:"
print recamanUntil [n = 15]
print ""
print "First duplicate Recaman number:"
print last recamanUntil [not? blnNew]</syntaxhighlight>
{{out}}
<pre>First 15 Recaman numbers:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicate Recaman number:
42</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f RECAMANS_SEQUENCE.AWK
# converted from Microsoft Small Basic
Line 431 ⟶ 476:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 440 ⟶ 485:
=={{header|BASIC}}==
<
20 PRINT "First 15 terms:"
30 FOR N=0 TO 14: GOSUB 100: PRINT A(N);: NEXT
Line 456 ⟶ 501:
140 NEXT
150 A(N)=X: RETURN
160 A(N)=A(N-1)+N: RETURN</
{{out}}
<pre>First 15 terms:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated term:
A( 24 ) = 42</pre>
==={{header|Applesoft BASIC}}===
{{trans|BASIC}}
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">10 DIM A(100)
20 PRINT "First 15 terms:"
30 FOR N=0 TO 14: GOSUB 100: PRINT A(N); " ";: NEXT
35 PRINT
40 PRINT "First repeated term:"
50 GOSUB 100
55 FOR M=0 TO N-1
56 IF A(M)=A(N) THEN 70
57 NEXT
60 N=N+1: GOTO 50
70 PRINT "A(";N;") = ";A(N)
80 END
100 IF N=0 THEN A(0)=0: RETURN
110 X = A(N-1)-N: IF X<0 THEN 160
120 FOR M=0 TO N-1
130 IF A(M)=X THEN 160
140 NEXT
150 A(N)=X: RETURN
160 A(N)=A(N-1)+N: RETURN</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
The [[#BASIC|BASIC]] solution works without any changes.
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
The [[#BASIC|BASIC]] solution works without any changes.
==={{header|Minimal BASIC}}===
{{trans|BASIC}}
{{works with|Quite BASIC}}
<syntaxhighlight lang="qbasic">10 DIM A(100)
20 PRINT "FIRST 15 TERMS:"
30 FOR N=0 TO 14
40 GOSUB 170
50 PRINT A(N);" ";
60 NEXT N
70 PRINT
80 PRINT "FIRST REPEATED TERM:"
90 GOSUB 170
100 FOR M=0 TO N-1
110 IF A(M)=A(N) THEN 150
120 NEXT M
130 LET N=N+1
140 GOTO 90
150 PRINT "A(";N;") = ";A(N)
160 STOP
170 IF N=0 THEN 280
180 LET X = A(N-1)-N
190 IF X<0 THEN 250
200 FOR M=0 TO N-1
210 IF A(M)=X THEN 250
220 NEXT M
230 LET A(N)=X
240 RETURN
250 LET A(N)=A(N-1)+N
260 RETURN
270 STOP
280 LET A(0)=0
290 RETURN
300 END</syntaxhighlight>
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
The [[#BASIC|BASIC]] solution works without any changes.
==={{header|Quite BASIC}}===
The [[#Minimal BASIC|Minimal BASIC]] solution works without any changes.
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
// Generate the N'th term of the Recaman sequence
// given terms 0 to N-1.
let generate(a, n) be
a!n := n=0 -> 0, valof
$( let subterm = a!(n-1) - n
let addterm = a!(n-1) + n
if subterm <= 0 resultis addterm
for i=0 to n-1
if a!i = subterm resultis addterm
resultis subterm
$)
let start() be
$( let a = vec 50 and n = 15 and rep = ?
writef("First %N members:*N", n)
for i = 0 to n-1
$( generate(a, i)
writef("%N ", a!i)
$)
writef("*NFirst repeated term:*N")
rep := valof
$( generate(a, n)
for i = 0 to n-1
if a!i = a!n resultis n
n := n + 1
$) repeat
writef("a!%N = %N*N", rep, a!rep)
$)</syntaxhighlight>
{{out}}
<pre>First 15 members:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated term:
a!24 = 42</pre>
=={{header|C}}==
{{libheader|GLib}}
{{trans|Go}}
<
#include <stdlib.h>
#include <gmodule.h>
Line 521 ⟶ 678:
free(a);
return 0;
}</
{{out}}
Line 532 ⟶ 689:
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<
using System.Collections.Generic;
Line 570 ⟶ 727:
}
}
}</
{{out}}
<pre>The first 15 terms of the Recaman sequence are: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
Line 578 ⟶ 735:
=={{header|C++}}==
{{trans|C#}}
<
#include <ostream>
#include <set>
Line 634 ⟶ 791:
return 0;
}</
{{out}}
<pre>The first 15 terms of the Recaman 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</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% 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</syntaxhighlight>
{{out}}
<pre>First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicated number: A(24) = 42
Terms needed to generate [0..1000]: 328002</pre>
=={{header|Comal}}==
<syntaxhighlight lang="comal">0010 DIM a#(0:100)
0020 //
0030 // Print the first 15 items
0040 PRINT "First 15 items: ",
0050 FOR i#:=0 TO 14 DO PRINT reca#(i#);
0060 PRINT
0070 //
0080 // Find and print the first repeated item
0090 i#:=15
0100 WHILE NOT find#(i#,reca#(i#)) DO i#:+1
0110 PRINT "First repeated item: A(",i#,") = ",a#(i#)
0120 //
0130 // Generate the n'th member of the Recaman sequence
0140 FUNC reca#(n#)
0150 IF n#=0 THEN RETURN 0
0160 a#(n#):=a#(n#-1)-n#
0180 IF a#(n#)<=0 OR find#(n#,a#(n#)) THEN a#(n#):=a#(n#-1)+n#
0190 RETURN a#(n#)
0200 ENDFUNC reca#
0210 //
0220 // See if a number occurs before the n'th member of the Recaman sequence
0230 FUNC find#(n#,num#)
0240 FOR x#:=0 TO n#-1 DO IF a#(x#)=num# THEN RETURN x#
0250 RETURN 0
0260 ENDFUNC find#
0270 END</syntaxhighlight>
{{out}}
<pre>First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated item: A(24) = 42</pre>
=={{header|COBOL}}==
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. RECAMAN.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 RECAMAN-SEQUENCE COMP.
02 A PIC 999 OCCURS 99 TIMES INDEXED BY I.
02 N PIC 999 VALUE 0.
01 VARIABLES COMP.
02 ADDC PIC S999.
02 SUBC PIC S999.
02 SPTR PIC 99 VALUE 1.
01 OUTPUT-FORMAT.
02 OUTI PIC Z9.
02 OUTN PIC BZ9.
02 OUTS PIC X(79).
PROCEDURE DIVISION.
BEGIN.
PERFORM GENERATE-NEXT-ITEM 15 TIMES.
PERFORM COLLATE-ITEM VARYING I FROM 1 BY 1
UNTIL I IS GREATER THAN 15.
DISPLAY 'First 15 items:' OUTS.
FIND-REPEATING.
PERFORM GENERATE-NEXT-ITEM.
SET I TO 1.
SEARCH A VARYING I
WHEN I IS NOT LESS THAN N
NEXT SENTENCE
WHEN A(I) IS EQUAL TO A(N)
SUBTRACT 1 FROM N GIVING OUTI
MOVE A(N) TO OUTN
DISPLAY 'First repeated item: A(' OUTI ') =' OUTN
STOP RUN.
GO TO FIND-REPEATING.
GENERATE-NEXT-ITEM.
IF N IS EQUAL TO ZERO
MOVE ZERO TO A(1)
ELSE
ADD N, A(N) GIVING ADDC
SUBTRACT N FROM A(N) GIVING SUBC
IF SUBC IS NOT GREATER THAN ZERO
MOVE ADDC TO A(N + 1)
ELSE
SET I TO 1
SEARCH A VARYING I
WHEN I IS NOT LESS THAN N
MOVE SUBC TO A(N + 1)
WHEN A(I) IS EQUAL TO SUBC
MOVE ADDC TO A(N + 1).
ADD 1 TO N.
COLLATE-ITEM.
MOVE A(I) TO OUTN.
STRING OUTN DELIMITED BY SIZE INTO OUTS WITH POINTER SPTR.</syntaxhighlight>
{{out}}
<pre>First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated item: A(24) = 42</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
void main() {
Line 680 ⟶ 1,017:
n++;
}
}</
{{out}}
<pre>The first 15 terms of the Recaman 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</pre>
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc nonrec find([*] int A; word top; int n) bool:
word i;
bool found;
i := 0;
found := false;
while i < top and not found do
found := A[i] = n;
i := i + 1
od;
found
corp
proc nonrec gen_next([*] int A; word n) int:
int add, sub;
add := A[n-1] + n;
sub := A[n-1] - n;
A[n] :=
if sub > 0 and not find(A, n, sub)
then sub
else add
fi;
A[n]
corp
proc nonrec main() void:
[30] int A;
word i;
A[0] := 0;
write("First 15 items: 0");
for i from 1 upto 14 do write(gen_next(A, i):3) od;
writeln();
while not find(A, i, gen_next(A, i)) do i := i + 1 od;
writeln("First repeated item: A(", i:2, ") = ", A[i]:2)
corp </syntaxhighlight>
{{out}}
<pre>First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated item: A(24) = 42</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
arrbase a[] 0
arrbase seen[] 0
len seen[] 100
#
a[] &= 0
seen[0] = 1
i = 1
repeat
h = a[i - 1] - i
if h <= 0 or seen[h] = 1
h = a[i - 1] + i
.
until seen[h] = 1
seen[h] = 1
a[] &= h
if i = 14
print a[]
.
i += 1
.
print h
</syntaxhighlight>
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<syntaxhighlight lang="forth">: array ( n -- ) ( i -- addr)
create cells allot
does> swap cells + ;
100 array sequence
: sequence. ( n -- ) cr 0 ?do i sequence @ . loop ;
: ?unused ( n -- t | n )
100 0 ?do
dup i sequence @ = if unloop exit then
loop drop true ;
: sequence-next ( n -- a[n] )
dup 0= if 0 0 sequence ! exit then ( case a[0]=0 )
dup dup 1- sequence @ swap - ( a[n]=a[n-1]-n )
dup dup 0> swap ?unused true = and if
nip exit then drop
dup 1- sequence @ swap + ; ( a[n]=a[n-1]+n )
: sequence-gen ( n -- )
0 ?do i sequence-next i sequence ! loop ;
: sequence-repeated
100 0 ?do
i 0 ?do
i sequence @ j sequence @ = if
cr ." first repeated : a[" i . ." ]=a[" j . ." ]=" i sequence @ . unloop unloop exit then
loop
loop ;
100 sequence-gen
15 sequence.
sequence-repeated</syntaxhighlight>
{{out}}
<pre>0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
first repeated : a[20 ]=a[24 ]=42 ok</pre>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 754 ⟶ 1,200:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>The first 15 terms are 0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 764 ⟶ 1,210:
=={{header|FOCAL}}==
<
01.20 F N=0,14;D 2;T %2,A(N)
01.30 T !"FIRST REPEATED"
Line 782 ⟶ 1,228:
02.50 I (Y)2.6,2.7,2.6
02.60 S A(N)=X;R
02.70 S A(N)=A(N-1)+N</
{{out}}
Line 792 ⟶ 1,238:
=={{header|Fōrmulæ}}==
'''Solution'''
The following snippet generates the Recaman's sequence of a given number of terms:
[[File:Fōrmulæ - Recamán's sequence 01.png]]
'''Case 1'''
* 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.
[[File:Fōrmulæ - Recamán's sequence 02.png]]
[[File:Fōrmulæ - Recamán's sequence 03.png]]
[[File:Fōrmulæ - Recamán's sequence 04.png]]
'''Case 2. Plotting the sequence'''
[[File:Fōrmulæ - Recamán's sequence 05.png]]
[[File:Fōrmulæ - Recamán's sequence 06.png]]
'''Case 3. Drawing the sequence as it was shown in the Numberphile video'''
[[File:Fōrmulæ - Recamán's sequence 07.png]]
[[File:Fōrmulæ - Recamán's sequence 08.png]]
[[File:Fōrmulæ - Recamán's sequence 09.png]]
=={{header|Go}}==
<
import "fmt"
Line 838 ⟶ 1,312:
}
}
}</
{{out}}
Line 850 ⟶ 1,324:
===Recursion===
A basic recursive function for the first N terms,
<
recaman n = fst <$> reverse (go n)
where
Line 865 ⟶ 1,339:
main :: IO ()
main = print $ recaman 15</
{{Out}}
<pre>[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]</pre>
Line 872 ⟶ 1,346:
Or, a little more flexibly, a '''recamanUpto''' (predicate) function.
{{Trans|JavaScript}}
<
import Data.Bool (bool)
Line 913 ⟶ 1,387:
, "Length of Recaman series required to include [0..1000]:"
, (show . length . recamanSuperset) $ fromList [0 .. 1000]
]</
{{Out}}
<pre>First 15 Recamans:
Line 929 ⟶ 1,403:
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.Maybe (fromJust)
import Data.Set (Set, fromList, insert, isSubsetOf, member)
Line 975 ⟶ 1,449:
"Length of Recaman series required to include [0..1000]:",
show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets
]</
{{Out}}
<pre>First 15 Recamans:
Line 1,027 ⟶ 1,501:
</pre>
Let's write a binary search adverb.
<syntaxhighlight lang="j">
average =: +/ % #
NB. extra_data u Bsearch bounds
Line 1,035 ⟶ 1,509:
NB. u is invoked as a dyad
Bsearch =: 1 :'((0 1 + (u <.@:average)) { ({. , <.@:average, {:)@:])^:_'
</syntaxhighlight>
<pre>
NB. f expresses "not all [0, 1000] are in the first y members of list x"
Line 1,054 ⟶ 1,528:
=={{header|Java}}==
{{Trans|Kotlin}}
<
import java.util.HashSet;
import java.util.List;
Line 1,098 ⟶ 1,572:
}
}
}</
{{out}}
<pre>The first 15 terms of the Recaman sequence are : [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
Line 1,106 ⟶ 1,580:
=={{header|JavaScript}}==
{{Trans|Haskell}}
<
const main = () => {
Line 1,191 ⟶ 1,665:
// MAIN ------------------------------------------------
return main();
})();</
{{Out}}
<pre>First 15 Recaman:
Line 1,202 ⟶ 1,676:
all integers from [0..1000]:
328002</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
Two jq solutions are provided here. The first is a monolithic "all-in-one" approach
in which a single function or procedure does all the work in one pass. This approach
has the disadvantage of neither providing or using reusable components.
The second solution is a stream-oriented one that separates the generation of the
sequence from other computations. This approach can be just as efficient as the
monolithic approach, but for the sake of illustration, the solution offered
here provides separate functions for generation and for each of the three specific tasks.
=== Monolithic approach===
'''Adapted from [[#Go|Go]]'''
The main point of potential interest in this implementation is that
the main function only retains the first few elements of the sequence
required to print them as an array.
<syntaxhighlight lang="jq">
# 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."</syntaxhighlight>
{{out}}
<pre>
The first 15 terms of 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 inclusive.
</pre>
=== A stream-oriented solution===
<syntaxhighlight lang="jq">
# Output: the stream of elements in the Recaman sequence, beginning with 0.
def recaman:
0,
foreach range(1; infinite) as $i ({used: {"0": true}, current: 0};
(.current - $i) as $next
| .current = (if ($next < 1 or .used[$next|tostring]) then $next + 2 * $i else $next end)
| .used[.current|tostring] = true;
.current );
# emit [.i, $x] for duplicated terms using IO==0
def duplicated(s):
foreach s as $x ({used: {}, i: -1};
.i += 1
| ($x|tostring) as $xs
| if .used[$xs] then .emit = [.i, $x] else .used[$xs] = true end;
select(.emit) | .emit);
# Input: an integer, $required
# s: a stream of non-negative integers
# Output: the index of the item in the stream s at which the stream up to and including
# that item includes all integers in the closed interval [0 .. $required].
#
def covers(s):
. as $required
| first(foreach s as $x ( { i: -1, found: {}, nfound: 0};
.i += 1
| ($x|tostring) as $xs
| if .found[$xs] then .
elif $x <= $required
then .found[$xs] = true | .nfound += 1
| if .nfound > $required then .emit=.i else . end
else .
end;
select(.emit).emit) );</syntaxhighlight>
'''The three tasks:'''
<syntaxhighlight lang="jq">
"First 15:", limit(15; recaman),
"\First duplicated:", first(duplicated(recaman)),
"\Index of first element to include 0 to 1000 inclusive:",
(1000|covers(recaman))
</syntaxhighlight>
{{out}}
<pre>
First 15:
0
1
3
6
2
7
13
20
12
21
11
22
10
23
9
First duplicated:
[24,42]
Index of first element to include 0 to 1000 inclusive:
328002
</pre>
=={{header|Julia}}==
{{trans|Go}}
<
a = Vector{Int}([0])
used = Dict{Int, Bool}(0 => true)
Line 1,235 ⟶ 1,852:
recaman()
</
The first 15 terms of the Recaman sequence are [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
The first duplicated term is a[25] = 42.
Line 1,243 ⟶ 1,860:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun main(args: Array<String>) {
Line 1,272 ⟶ 1,889:
n++
}
}</
{{output}}
Line 1,284 ⟶ 1,901:
This runs out of memory determining the final part :(
{{trans|C++}}
<
local used = {[0]=true}
local used1000 = {[0]=true}
Line 1,318 ⟶ 1,935:
end
n = n + 1
end</
{{out}}
<pre>The first 15 terms of the Recaman 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
lua: not enough memory</pre>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
VECTOR VALUES ELEMF = $2HA(,I2,4H) = ,I2*$
DIMENSION A(100)
A(0) = 0
PRINT COMMENT $ FIRST 15 ELEMENTS$
PRINT FORMAT ELEMF,0,0
THROUGH EL, FOR I=1, 1, I.GE.15
EL PRINT FORMAT ELEMF,I,NEXT.(I)
PRINT COMMENT $ $
PRINT COMMENT $ FIRST REPEATED ELEMENT$
RPT THROUGH RPT, FOR I=I, 1, FIND.(I,NEXT.(I))
PRINT FORMAT ELEMF,I,A(I)
INTERNAL FUNCTION(N,TOP)
ENTRY TO FIND.
FI=0
SRCH WHENEVER FI.GE.TOP, FUNCTION RETURN 0B
WHENEVER A(FI).E.N, FUNCTION RETURN 1B
FI=FI+1
TRANSFER TO SRCH
END OF FUNCTION
INTERNAL FUNCTION(N)
ENTRY TO NEXT.
HI=A(N-1)+N
LO=A(N-1)-N
WHENEVER LO.L.0
A(N)=HI
OR WHENEVER FIND.(LO,N)
A(N)=HI
OTHERWISE
A(N)=LO
END OF CONDITIONAL
FUNCTION RETURN A(N)
END OF FUNCTION
END OF PROGRAM </syntaxhighlight>
{{out}}
<pre>FIRST 15 ELEMENTS
A( 0) = 0
A( 1) = 1
A( 2) = 3
A( 3) = 6
A( 4) = 2
A( 5) = 7
A( 6) = 13
A( 7) = 20
A( 8) = 12
A( 9) = 21
A(10) = 11
A(11) = 22
A(12) = 10
A(13) = 23
A(14) = 9
FIRST REPEATED ELEMENT
A(20) = 42</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[f]
f[s_List] := Block[{a = s[[-1]], len = Length@s},
Append[s, If[a > len && ! MemberQ[s, a - len], a - len, a + len]]]; g = Nest[f, {0}, 70]
g = Nest[f, {0}, 70];
Take[g, 15]
p = Select[Tally[g], Last /* EqualTo[2]][[All, 1]]
p = Flatten[Position[g, #]] & /@ p;
TakeSmallestBy[p, Last, 1][[1]]</syntaxhighlight>
{{out}}
<pre>{0,1,3,6,2,7,13,20,12,21,11,22,10,23,9}
{43,42,79,78}
{21,25}</pre>
=={{header|Microsoft Small Basic}}==
Inefficency of associative array allocation in Small Basic ban to provide the optional task.
<
nn=15
TextWindow.WriteLine("Recaman's sequence for the first " + nn + " numbers:")
Line 1,369 ⟶ 2,060:
EndFor
exitsub:
EndSub </
{{out}}
<pre>
Line 1,378 ⟶ 2,069:
=={{header|Nim}}==
<
iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] =
Line 1,404 ⟶ 2,095:
if target.card == 0:
echo "All numbers from 0 to 1000 generated after $1 terms.".format(n)
break</
{{out}}
Line 1,413 ⟶ 2,104:
=={{header|Objeck}}==
{{trans|Java}}
<
class RecamanSequence {
Line 1,472 ⟶ 2,163:
return out;
}
}</
{{output}}
Line 1,482 ⟶ 2,173:
=={{header|Perl}}==
<
$max = 1000;
Line 1,503 ⟶ 2,194:
print "First fifteen terms of Recaman's sequence: " . join(' ', @recamans[0..14]) . "\n";
print "First duplicate at term: a[$dup]\n";
print "Range 0..1000 covered by terms up to a[$term]\n";</
{{out}}
<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 1,511 ⟶ 2,202:
=={{header|Phix}}==
{{trans|D}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">found_duplicate</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000000;">used</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- (grows to 1,942,300 entries)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">all_used</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">15</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found_duplicate</span> <span style="color: #008080;">or</span> <span style="color: #000000;">all_used</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1000</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">next</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">padlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">already_used</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">padlen</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">already_used</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">padlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">used</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">padlen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">all_used</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">all_used</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">all_used</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">15</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 15 terms of the Recaman sequence are: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">already_used</span> <span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found_duplicate</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first duplicated term is a[%d] = %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">found_duplicate</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">all_used</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1000</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Terms up to a[%d] are needed to generate 0 to 1000\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">});</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,553 ⟶ 2,245:
=={{header|PHP}}==
{{trans|Java}}
<
$a = array();
array_push($a, 0);
Line 1,598 ⟶ 2,290:
$n++;
}
</syntaxhighlight>
{{out}}
Line 1,606 ⟶ 2,298:
Terms up to a[328002] are needed to generate 0 to 1000
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pli">recaman: procedure options(main);
declare A(0:30) fixed;
/* is X in the first N terms of the Recaman sequence? */
find: procedure(x, n) returns(bit);
declare (x, n, i) fixed;
do i=0 to n-1;
if A(i)=x then return('1'b);
end;
return('0'b);
end find;
/* generate the N'th term of the Recaman sequence */
generate: procedure(n) returns(fixed);
declare n fixed;
if n=0 then
A(0) = 0;
else do;
declare (sub, add) fixed;
sub = A(n-1) - n;
add = A(n-1) + n;
/* A(n-1) - n not positive? */
if sub <= 0 then
A(n) = add;
/* A(n-1) - n already generated? */
else if find(sub, n) then
A(n) = add;
else
A(n) = sub;
end;
return(A(n));
end generate;
declare i fixed;
put skip list('First 15 members:');
do i=0 to 14;
put edit(generate(i)) (F(3));
end;
put skip list('First repeated term: ');
do i=15 repeat(i+1) while(^find(generate(i), i)); end;
put edit('A(',i,') = ',A(i)) (A,F(2),A,F(2));
end recaman;</syntaxhighlight>
{{out}}
<pre>First 15 members: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First repeated term: A(24) = 42</pre>
=={{header|PL/M}}==
<syntaxhighlight lang="pli">100H:
BDOS: PROCEDURE(F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT$CH: PROCEDURE(C); DECLARE C BYTE; CALL BDOS(2,C); END PRINT$CH;
PRINT$STR: PROCEDURE(S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT$STR;
/* PRINT NUMBER */
PRINT$NUM: PROCEDURE(N);
DECLARE (N, P) ADDRESS, C BASED P BYTE;
DECLARE S(6) BYTE INITIAL('.....$');
P = .S(5);
DIGIT:
P = P-1;
C = '0' + N MOD 10;
N = N/10;
IF N>0 THEN GO TO DIGIT;
CALL PRINT$STR(P);
END PRINT$NUM;
/* IS X IN THE FIRST N TERMS OF THE SEQUENCE */
FIND: PROCEDURE(SEQ,X,N) BYTE;
DECLARE SEQ ADDRESS, (I, X, N, A BASED SEQ) BYTE;
DO I=0 TO N-1;
IF A(I)=X THEN RETURN 0FFH;
END;
RETURN 0;
END FIND;
/* GENERATE THE N'TH TERM OF THE SEQUENCE */
GENERATE: PROCEDURE(SEQ,N) BYTE;
DECLARE SEQ ADDRESS, (N, A BASED SEQ) BYTE;
IF N=0 THEN
A(N)=0;
ELSE DO;
DECLARE (SUB, ADD) BYTE;
SUB = A(N-1) - N;
ADD = A(N-1) + N;
/* A(N-1) - N NEGATIVE? */
IF A(N-1) <= N THEN
A(N) = ADD;
/* A(N-1) - N ALREADY GENERATED? */
ELSE IF FIND(SEQ,SUB,N) THEN
A(N) = ADD;
ELSE
A(N) = SUB;
END;
RETURN A(N);
END GENERATE;
DECLARE I BYTE, A(30) BYTE;
CALL PRINT$STR(.'FIRST 15 MEMBERS: $');
DO I=0 TO 14;
CALL PRINT$NUM(GENERATE(.A, I));
CALL PRINT$CH(' ');
END;
CALL PRINT$STR(.(13,10,'FIRST REPEATED TERM: A($'));
I=15;
DO WHILE NOT FIND(.A, GENERATE(.A, I), I);
I = I+1;
END;
CALL PRINT$NUM(I);
CALL PRINT$STR(.') = $');
CALL PRINT$NUM(A(I));
CALL PRINT$STR(.(13,10,'$'));
CALL EXIT;
EOF</syntaxhighlight>
{{out}}
<pre>FIRST 15 MEMBERS: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
FIRST REPEATED TERM: A(24) = 42</pre>
=={{header|PureBasic}}==
<
Dim a.i(#MAX)
Dim b.b(1)
Line 1,633 ⟶ 2,446:
PrintN("Number of Recaman terms needed to generate all integers from [0..1000]: "+Str(fit1000))
Input()
End</
{{out}}
<pre>First 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 1,642 ⟶ 2,455:
=={{header|Python}}==
===Conditional iteration over a generator===
<
class Recamans():
Line 1,683 ⟶ 2,496:
if setn.issubset(recamans.a):
print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})")
break</
{{out}}
Line 1,694 ⟶ 2,507:
( This turns out to be c. 8X faster than than the ''iteration over generator'' approach above, on a simple start to end measure using ''time.time()'')
<
Line 1,760 ⟶ 2,573:
if __name__ == '__main__':
main()</
{{Out}}
<pre>First 15 Recaman:
Line 1,776 ⟶ 2,589:
( This version is still c. 8X faster than the ''conditional iteration over generator'' version, as measured by a simple start and end test using ''time.time()'' ).
<
from itertools import (islice)
Line 1,885 ⟶ 2,698:
# MAIN ---
if __name__ == '__main__':
main()</
<pre>First 15 Recaman:
[0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
Line 1,892 ⟶ 2,705:
Number of Recaman terms needed to generate all integers from [0..1000]:
328002</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ stack 0 ] is seennumbers ( --> s )
[ bit seennumbers take
| seennumbers put ] is seen ( n --> )
[ dup 0 < iff
[ drop true ] done
bit seennumbers share
& 0 != ] is seen? ( n --> b )
[ 1+ bit 1 -
seennumbers share
over & = ] is allseen? ( n --> b )
[ stack [ ] ] is repeats ( --> s )
[ 1 seennumbers replace
[] repeats replace
' [ 0 ] 1 ] is startseq ( --> [ n )
[ over -1 peek
over - dup seen? if
[ over 2 * +
dup seen? if
[ repeats take
over join
repeats put ] ]
dup seen
swap dip join
1+ ] is nextterm ( [ n --> [ n )
say "first 15 terms: "
startseq
14 times nextterm
drop echo cr
say "first duplicated term: "
startseq
[ repeats share [] = while
nextterm
again ]
drop -1 peek echo cr
say "terms needed to generate 0 to 1000: "
startseq
[ nextterm
1000 allseen? until ]
nip 1 - echo cr
</syntaxhighlight>
{{out}}
<pre>first 15 terms: [ 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 ]
first duplicated term: 42
terms needed to generate 0 to 1000: 328002
</pre>
=={{header|R}}==
A bit slow because the append() function is expensive.
<
visited <- vector('logical', 1e8)
Line 1,937 ⟶ 2,811:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,949 ⟶ 2,823:
{{works with|Rakudo|2018.06}}
<syntaxhighlight lang="raku"
state %seen;
state $term;
Line 1,969 ⟶ 2,843:
@seen[$this] = 1;
say "Range 0..1000 covered by terms up to a[{$i - 1}]" and last if ++$ == 1001;
}</
{{out}}
<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 1,985 ⟶ 2,859:
could've been replaced with:
if !.z | z<0 then z= _ + #
<
parse arg N h . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/
Line 2,010 ⟶ 2,884:
end
$= $ z /*add number to $ list?*/
end /*#*/; return $ /*return the $ list. */</
{{out|output|text= when using the default input:}}
Line 2,023 ⟶ 2,897:
===version 2===
<
/*improved using version 1's method for task 3 */
Call time 'R' /* Start timer */
Line 2,068 ⟶ 2,942:
Have.temp=1
End
Return s</
{{out}}
<pre>the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 2,076 ⟶ 2,950:
=={{header|Ring}}==
<
load "zerolib.ring"
Line 2,126 ⟶ 3,000:
see "" + dupnr + "] = " + duplicate + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 2,134 ⟶ 3,008:
the first duplicated term is a[24] = 42
done...
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
1 + RKMSQ SWAP OVER SIZE
'''IF''' DUP2 ≤
'''THEN''' DROP GET
'''ELSE''' SWAP 1 - '''FOR''' j
DUP DUP SIZE GET j -
'''IF''' DUP2 ABS POS OVER 0 < OR
'''THEN''' j 2 * + '''END'''
+ '''NEXT'''
DUP ‘'''RKMSQ'''‘ STO DUP SIZE GET '''END'''
≫ ‘'''RECAM'''’ STO
≪ 0 { 0 } ‘'''RKMSQ'''’ STO
'''DO'''
1 + '''RKMSQ''' OVER '''RECAM'''
'''UNTIL''' POS '''END RECAM'''
≫ ‘'''TASK2'''’ STO
|
''' RECAM''' ''( n -- a(n) )''
get m = size of sequence in memory
if n+1 ≤ m
then recall sequence(n+1)=a(n)
else for j=m to n
get a(j-1)-n
if already in sequence or <0
then a(j) = (a(j-1)-n)+2*n
add to sequence
store updated sequence and recall a(n)
.
.
Initialize variables
Loop
get a(n)
until a(n) already in sequence
.
|}
{{in}}
<pre>
{ 0 } 'RKMSQ’ STO
15 RECAM
RKMSQ
{ 0 } ‘RKMSQ’ STO
TASK2
</pre>
{{out}}
<pre>
3: 24
2: { 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 }
1: 42
</pre>
=={{header|Ruby}}==
{{trans|Kotlin}}
<
a = [0]
Line 2,169 ⟶ 3,101:
end
n = n + 1
end</
{{out}}
<pre>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</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use std::collections::HashSet ;
fn main() {
let mut recamans : Vec<i32> = Vec::new( ) ;
let mut reca_set : HashSet<i32> = HashSet::new() ;
let mut first_nums : HashSet<i32> = HashSet::new( ) ;
for i in 0i32..=1000 {
first_nums.insert( i ) ;
}
recamans.push( 0 ) ;
reca_set.insert( 0 ) ;
let mut current : i32 = 0 ;
while ! first_nums.is_subset( &reca_set ) {
current += 1 ;
let mut nextnum : i32 = recamans[( current as usize ) - 1] - current ;
if nextnum < 0 || reca_set.contains( &nextnum ) {
nextnum = recamans[(current as usize ) - 1 ] + current ;
}
recamans.push( nextnum ) ;
reca_set.insert( nextnum ) ;
if current == 15 {
println!("The first 15 numbers of the Recaman sequence are:" ) ;
println!("{:?}" , recamans ) ;
}
}
println!("To generate all numbers from 0 to 1000 , one has to go to element {}" , current) ;
}</syntaxhighlight>
{{Out}}
<pre>
The first 15 numbers of the Recaman sequence are:
[0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24]
To generate all numbers from 0 to 1000 , one has to go to element 328002
</pre>
=={{header|Scala}}==
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/xjLHy7m/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/FdJaIB68S8i5OSndpigBtA Scastie (remote JVM)].
<
object RecamansSequence extends App {
Line 2,205 ⟶ 3,173:
println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}")
}</
=={{header|Scheme}}==
{{works with|Chez Scheme}}
<syntaxhighlight lang="scheme">; Create a dynamically resizing vector (a "dynvec").
; Returns a procedure that takes a variable number of arguments:
; 0 : () --> Returns the vector from index 0 through the maximum index set.
; 1 : (inx) --> Returns the value at the given index.
; 2 : (inx val) --> Sets the given value into the given index, and returns the value.
(define make-dynvec
(lambda (init-size extra-fact init-val)
(let ((vec (make-vector init-size init-val)) (maxinx -1))
(lambda args
(if (null? args)
(let ((retvec (make-vector (1+ maxinx))))
(do ((index 0 (1+ index)))
((> index maxinx) retvec)
(vector-set! retvec index (vector-ref vec index))))
(let ((inx (car args)))
(when (>= inx (vector-length vec))
(let ((newvec (make-vector
(inexact->exact (ceiling (* extra-fact inx)))
init-val)))
(do ((index 0 (1+ index)))
((>= index (vector-length vec)))
(vector-set! newvec index (vector-ref vec index)))
(set! vec newvec)))
(when (pair? (cdr args))
(when (> inx maxinx) (set! maxinx inx))
(vector-set! vec inx (cadr args)))
(vector-ref vec inx)))))))
; Generate the Recaman's sequence.
; Generate the terms of Recaman's sequence until the given "stop" procedure
; returns a true value; that returned value becomes the value of this procedure.
; The arguments to the "stop" procedure are: n, the value of the n'th term,
; #t if that term was seen before, #t if the term was arrived at by addition,
; the Recaman's sequence so far (as a dynvec), and a dynvec of the n's at which
; a value was first seen or #f if not previously seen ("seen1st").
(define recaman-sequence
(lambda (stop-proc)
(let ((recaman (make-dynvec 10 2 0))
(seen1st (make-dynvec 10 2 #f)))
(do ((n 0 (1+ n)) (done-retval #f))
(done-retval done-retval)
(if (= n 0)
(begin
(recaman n 0)
(seen1st 0 n)
(set! done-retval (stop-proc n 0 #f #f recaman seen1st)))
(let ((try-sub (- (recaman (1- n)) n)))
(if (and (> try-sub 0) (not (seen1st try-sub)))
(begin
(recaman n try-sub)
(seen1st try-sub n)
(set! done-retval (stop-proc n try-sub #f #f recaman seen1st)))
(let* ((val-add (+ (recaman (1- n)) n)) (seen-prev (seen1st val-add)))
(recaman n val-add)
(unless (seen1st val-add) (seen1st val-add n))
(set! done-retval
(stop-proc n val-add seen-prev #t recaman seen1st))))))))))
; Generate and display the first 15 Recaman's numbers.
(printf "First 15 Recaman's numbers: ~a~%"
(recaman-sequence (lambda (n val seen-prev by-add recaman seen1st)
(and (>= n (1- 15)) (recaman)))))
; Find and display the first duplicated Recaman's number.
; The only way to be a duplicate is if the number was arrived
; at by adding 'n' and the number has been seen before.
(let ((dup-n-val-1st
(recaman-sequence (lambda (n val seen-prev by-add recaman seen1st)
(and by-add seen-prev (list n val (seen1st val)))))))
(printf "First duplicate Recaman's number: a[~a] = a[~a] = ~a~%"
(caddr dup-n-val-1st) (car dup-n-val-1st) (cadr dup-n-val-1st)))
; Find and display how many terms of the sequence are needed
; for all the integers 0..1000, inclusive, to be generated.
(let* ((all-first 1001)
(terms-to-gen-all (recaman-sequence
(lambda (n val seen-prev by-add recaman seen1st)
(do ((inx 0 (1+ inx)))
((or (>= inx all-first) (not (seen1st inx)))
(and (>= inx all-first) (1+ n))))))))
(printf
"Terms of Recaman's sequence to generate all integers 0..~a, inclusive: ~a~%"
(1- all-first) terms-to-gen-all))</syntaxhighlight>
{{out}}
<pre>First 15 Recaman's numbers: #(0 1 3 6 2 7 13 20 12 21 11 22 10 23 9)
First duplicate Recaman's number: a[20] = a[24] = 42
Terms of Recaman's sequence to generate all integers 0..1000, inclusive: 328003</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program recaman;
a := {[0,0]};
loop for i in [1..14] do
extend(a);
end loop;
print("First 15:", [a(n) : n in [0..14]]);
loop
doing n := extend(a);
until #(rept:=[[r,i] : r = a(i) | r=n]) > 1
do pass;
end loop;
print("First repetition:", n, "at", {x:x in rept}{n});
proc extend(rw a);
n := max/ domain a;
t := a(n) - n-1;
if t<0 or t in range a then
t := a(n) + n+1;
end if;
return a(n+1) := t;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>First 15: [0 1 3 6 2 7 13 20 12 21 11 22 10 23 9]
First repetition: 42 at {20 24}</pre>
=={{header|Sidef}}==
<
var term = 0
Line 2,253 ⟶ 3,345:
}
}
}</
{{out}}
<pre>First 15 terms of the Recaman's sequence: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9
Line 2,260 ⟶ 3,352:
=={{header|uBasic/4tH}}==
<
Print "First 15 numbers:"
For i = 1 Step 1 ' start loop
If i<16 Then Print a, ' print first 15 numbers
b = Iif ((a-i<1) + (Func(_Peek(Max(0, a-i)))), a+i, a-i)
If
Proc _Set(Set(a, b)) ' set bit in bitmap
Next
Line 2,275 ⟶ 3,366:
_Poke Param(2) : Return (Or(@(a@), Shl(1, b@)))
_Peek Param(1) : Return (And(@(a@/32), Shl(1, a@%32))>0)
</syntaxhighlight>
{{out}}
<pre>
Line 2,288 ⟶ 3,379:
{{trans|Rexx}}
To run in console mode with cscript.
<
nx=15
h=1000
Line 2,345 ⟶ 3,436:
next 'n
recaman=list
end function 'recaman</
{{out}}
<pre>
Line 2,356 ⟶ 3,447:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Collections.Generic
Line 2,380 ⟶ 3,471:
Next
End Sub
End Module</
<pre>The first 15 terms of the Recamán 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
Line 2,387 ⟶ 3,478:
=={{header|Wren}}==
{{trans|Kotlin}}
<
var used = { 0: true }
var used1000 = { 0: true }
Line 2,410 ⟶ 3,501:
}
n = n + 1
}</
{{out}}
Line 2,421 ⟶ 3,512:
=={{header|zkl}}==
<
Walker.tweak(fcn(rn,rp,d){
n,p,a := rn.value, rp.value, p - n;
Line 2,428 ⟶ 3,519:
return(rn.inc(),a,d[a]>1);
}.fp(Ref(0),Ref(0),Dictionary()) )
}</
<
recamanW().walk(15).apply("get",1).println();
Line 2,437 ⟶ 3,528:
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));</
{{out}}
<pre>
|