Recaman's sequence: Difference between revisions
m
typo
Not a robot (talk | contribs) m (→{{header|BASIC}}: syntax highlighting) |
m (typo) |
||
| (16 intermediate revisions by 12 users not shown) | |||
Line 2:
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
If the conditions ''don't'' hold then <code>a(n) = a(n-1) + n</code>.
Line 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 21 ⟶ 22:
{{trans|Python}}
<
‘The successor for a given Recaman term,
given the set of Recaman terms seen so far.’
Line 50 ⟶ 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 63 ⟶ 64:
=={{header|ALGOL W}}==
<
% calculate Recaman's sequence values %
Line 152 ⟶ 153:
end
end.</
{{out}}
<pre>
Line 163 ⟶ 164:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
genNext←{
R←⍵[N-1]-N←≢⍵
Line 175 ⟶ 176:
⎕←'Length of sequence containing [0..1000]:'
⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca
}</
{{out}}
Line 190 ⟶ 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 377 ⟶ 378:
on unwords(xs)
intercalateS(space, xs)
end unwords</
{{Out}}
<pre>First 15 Recamans:
Line 390 ⟶ 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 436 ⟶ 476:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 445 ⟶ 485:
=={{header|BASIC}}==
<
20 PRINT "First 15 terms:"
30 FOR N=0 TO 14: GOSUB 100: PRINT A(N);: NEXT
Line 461 ⟶ 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}}==
<
// Generate the N'th term of the Recaman sequence
Line 503 ⟶ 615:
writef("a!%N = %N*N", rep, a!rep)
$)</
{{out}}
<pre>First 15 members:
Line 513 ⟶ 625:
{{libheader|GLib}}
{{trans|Go}}
<
#include <stdlib.h>
#include <gmodule.h>
Line 566 ⟶ 678:
free(a);
return 0;
}</
{{out}}
Line 577 ⟶ 689:
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<
using System.Collections.Generic;
Line 615 ⟶ 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 623 ⟶ 735:
=={{header|C++}}==
{{trans|C#}}
<
#include <ostream>
#include <set>
Line 679 ⟶ 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]
Line 686 ⟶ 798:
=={{header|CLU}}==
<
recaman = cluster is new, fetch
rep = array[int]
Line 764 ⟶ 876:
|| int$unparse(n))
end
end start_up</
{{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}}==
<
PROGRAM-ID. RECAMAN.
Line 829 ⟶ 972:
COLLATE-ITEM.
MOVE A(I) TO OUTN.
STRING OUTN DELIMITED BY SIZE INTO OUTS WITH POINTER SPTR.</
{{out}}
<pre>First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 836 ⟶ 979:
=={{header|D}}==
{{trans|Kotlin}}
<
void main() {
Line 874 ⟶ 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]
Line 881 ⟶ 1,024:
=={{header|Draco}}==
<
word i;
bool found;
Line 916 ⟶ 1,059:
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 </
{{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 989 ⟶ 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 999 ⟶ 1,210:
=={{header|FOCAL}}==
<
01.20 F N=0,14;D 2;T %2,A(N)
01.30 T !"FIRST REPEATED"
Line 1,017 ⟶ 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 1,027 ⟶ 1,238:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Recam%C3%A1n%27s_sequence}}
'''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 1,073 ⟶ 1,312:
}
}
}</
{{out}}
Line 1,085 ⟶ 1,324:
===Recursion===
A basic recursive function for the first N terms,
<
recaman n = fst <$> reverse (go n)
where
Line 1,100 ⟶ 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 1,107 ⟶ 1,346:
Or, a little more flexibly, a '''recamanUpto''' (predicate) function.
{{Trans|JavaScript}}
<
import Data.Bool (bool)
Line 1,148 ⟶ 1,387:
, "Length of Recaman series required to include [0..1000]:"
, (show . length . recamanSuperset) $ fromList [0 .. 1000]
]</
{{Out}}
<pre>First 15 Recamans:
Line 1,164 ⟶ 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 1,210 ⟶ 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,262 ⟶ 1,501:
</pre>
Let's write a binary search adverb.
<syntaxhighlight lang="j">
average =: +/ % #
NB. extra_data u Bsearch bounds
Line 1,270 ⟶ 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,289 ⟶ 1,528:
=={{header|Java}}==
{{Trans|Kotlin}}
<
import java.util.HashSet;
import java.util.List;
Line 1,333 ⟶ 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,341 ⟶ 1,580:
=={{header|JavaScript}}==
{{Trans|Haskell}}
<
const main = () => {
Line 1,426 ⟶ 1,665:
// MAIN ------------------------------------------------
return main();
})();</
{{Out}}
<pre>First 15 Recaman:
Line 1,457 ⟶ 1,696:
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]
Line 1,503 ⟶ 1,742:
| "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."</
{{out}}
<pre>
Line 1,511 ⟶ 1,750:
</pre>
=== A stream-oriented solution===
<syntaxhighlight lang="jq">
# Output: the stream of elements in the Recaman sequence, beginning with 0.
def recaman:
Line 1,545 ⟶ 1,784:
else .
end;
select(.emit).emit) );</
'''The three tasks:'''
<syntaxhighlight lang="jq">
"First 15:", limit(15; recaman),
Line 1,554 ⟶ 1,793:
"\Index of first element to include 0 to 1000 inclusive:",
(1000|covers(recaman))
</syntaxhighlight>
{{out}}
<pre>
Line 1,583 ⟶ 1,822:
=={{header|Julia}}==
{{trans|Go}}
<
a = Vector{Int}([0])
used = Dict{Int, Bool}(0 => true)
Line 1,613 ⟶ 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,621 ⟶ 1,860:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun main(args: Array<String>) {
Line 1,650 ⟶ 1,889:
n++
}
}</
{{output}}
Line 1,662 ⟶ 1,901:
This runs out of memory determining the final part :(
{{trans|C++}}
<
local used = {[0]=true}
local used1000 = {[0]=true}
Line 1,696 ⟶ 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
Line 1,703 ⟶ 1,942:
=={{header|MAD}}==
<
VECTOR VALUES ELEMF = $2HA(,I2,4H) = ,I2*$
DIMENSION A(100)
Line 1,740 ⟶ 1,979:
FUNCTION RETURN A(N)
END OF FUNCTION
END OF PROGRAM </
{{out}}
<pre>FIRST 15 ELEMENTS
Line 1,763 ⟶ 2,002:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
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]
Line 1,770 ⟶ 2,009:
p = Select[Tally[g], Last /* EqualTo[2]][[All, 1]]
p = Flatten[Position[g, #]] & /@ p;
TakeSmallestBy[p, Last, 1][[1]]</
{{out}}
<pre>{0,1,3,6,2,7,13,20,12,21,11,22,10,23,9}
Line 1,778 ⟶ 2,017:
=={{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,821 ⟶ 2,060:
EndFor
exitsub:
EndSub </
{{out}}
<pre>
Line 1,830 ⟶ 2,069:
=={{header|Nim}}==
<
iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] =
Line 1,856 ⟶ 2,095:
if target.card == 0:
echo "All numbers from 0 to 1000 generated after $1 terms.".format(n)
break</
{{out}}
Line 1,865 ⟶ 2,104:
=={{header|Objeck}}==
{{trans|Java}}
<
class RecamanSequence {
Line 1,924 ⟶ 2,163:
return out;
}
}</
{{output}}
Line 1,934 ⟶ 2,173:
=={{header|Perl}}==
<
$max = 1000;
Line 1,955 ⟶ 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,963 ⟶ 2,202:
=={{header|Phix}}==
{{trans|D}}
<!--<
<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>
Line 1,996 ⟶ 2,235:
<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>
<!--</
{{out}}
<pre>
Line 2,006 ⟶ 2,245:
=={{header|PHP}}==
{{trans|Java}}
<
$a = array();
array_push($a, 0);
Line 2,051 ⟶ 2,290:
$n++;
}
</syntaxhighlight>
{{out}}
Line 2,061 ⟶ 2,300:
=={{header|PL/I}}==
<
declare A(0:30) fixed;
Line 2,103 ⟶ 2,342:
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;</
{{out}}
<pre>First 15 members: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 2,109 ⟶ 2,348:
=={{header|PL/M}}==
<
BDOS: PROCEDURE(F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
Line 2,176 ⟶ 2,415:
CALL PRINT$STR(.(13,10,'$'));
CALL EXIT;
EOF</
{{out}}
<pre>FIRST 15 MEMBERS: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
Line 2,182 ⟶ 2,421:
=={{header|PureBasic}}==
<
Dim a.i(#MAX)
Dim b.b(1)
Line 2,207 ⟶ 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 2,216 ⟶ 2,455:
=={{header|Python}}==
===Conditional iteration over a generator===
<
class Recamans():
Line 2,257 ⟶ 2,496:
if setn.issubset(recamans.a):
print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})")
break</
{{out}}
Line 2,268 ⟶ 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 2,334 ⟶ 2,573:
if __name__ == '__main__':
main()</
{{Out}}
<pre>First 15 Recaman:
Line 2,350 ⟶ 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 2,459 ⟶ 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 2,469 ⟶ 2,708:
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ stack 0 ] is seennumbers ( --> s )
Line 2,518 ⟶ 2,757:
1000 allseen? until ]
nip 1 - echo cr
</syntaxhighlight>
{{out}}
Line 2,530 ⟶ 2,769:
=={{header|R}}==
A bit slow because the append() function is expensive.
<
visited <- vector('logical', 1e8)
Line 2,572 ⟶ 2,811:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,584 ⟶ 2,823:
{{works with|Rakudo|2018.06}}
<syntaxhighlight lang="raku"
state %seen;
state $term;
Line 2,604 ⟶ 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 2,620 ⟶ 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,645 ⟶ 2,884:
end
$= $ z /*add number to $ list?*/
end /*#*/; return $ /*return the $ list. */</
{{out|output|text= when using the default input:}}
Line 2,658 ⟶ 2,897:
===version 2===
<
/*improved using version 1's method for task 3 */
Call time 'R' /* Start timer */
Line 2,703 ⟶ 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,711 ⟶ 2,950:
=={{header|Ring}}==
<
load "zerolib.ring"
Line 2,761 ⟶ 3,000:
see "" + dupnr + "] = " + duplicate + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 2,769 ⟶ 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,804 ⟶ 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,840 ⟶ 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,888 ⟶ 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,895 ⟶ 3,352:
=={{header|uBasic/4tH}}==
<
Print "First 15 numbers:"
Line 2,909 ⟶ 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,922 ⟶ 3,379:
{{trans|Rexx}}
To run in console mode with cscript.
<
nx=15
h=1000
Line 2,979 ⟶ 3,436:
next 'n
recaman=list
end function 'recaman</
{{out}}
<pre>
Line 2,990 ⟶ 3,447:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Collections.Generic
Line 3,014 ⟶ 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 3,021 ⟶ 3,478:
=={{header|Wren}}==
{{trans|Kotlin}}
<
var used = { 0: true }
var used1000 = { 0: true }
Line 3,044 ⟶ 3,501:
}
n = n + 1
}</
{{out}}
Line 3,055 ⟶ 3,512:
=={{header|zkl}}==
<
Walker.tweak(fcn(rn,rp,d){
n,p,a := rn.value, rp.value, p - n;
Line 3,062 ⟶ 3,519:
return(rn.inc(),a,d[a]>1);
}.fp(Ref(0),Ref(0),Dictionary()) )
}</
<
recamanW().walk(15).apply("get",1).println();
Line 3,071 ⟶ 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>
| |||