Recaman's sequence: Difference between revisions
m typo |
|||
(42 intermediate revisions by 20 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
The '''[[wp:Recamán's sequence|Recamán's sequence]]''' generates Natural numbers. |
The '''[[wp:Recamán's sequence|Recamán's sequence]]''' generates Natural numbers. |
||
Starting from zero, the n'th term <code>a(n)</code> 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 previousely generated.<br> |
|||
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>. |
If the conditions ''don't'' hold then <code>a(n) = a(n-1) + n</code>. |
||
;Task: |
;Task: |
||
# Generate and show here the first 15 members of the sequence. |
# Generate and show here the first 15 members of the sequence. |
||
# Find and show here, the first duplicated number in the sequence. |
# Find and show here, the first duplicated number in the sequence. |
||
# '''Optionally''': Find and show here, |
# '''Optionally''': Find and show here, how many terms of the sequence are needed until all the integers 0..1000, inclusive, are generated. |
||
Line 14: | Line 16: | ||
* [https://oeis.org/A005132 A005132], The On-Line Encyclopedia of Integer Sequences. |
* [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://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> |
<br><br> |
||
Line 19: | Line 22: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F recamanSucc(seen, n, r) |
||
‘The successor for a given Recaman term, |
‘The successor for a given Recaman term, |
||
given the set of Recaman terms seen so far.’ |
given the set of Recaman terms seen so far.’ |
||
Line 48: | Line 51: | ||
print("First duplicated Recaman:\n "recamanUntil((seen, n, r, blnNew) -> !blnNew).last) |
print("First duplicated Recaman:\n "recamanUntil((seen, n, r, blnNew) -> !blnNew).last) |
||
V setK = Set(enumFromTo(0)(1000)) |
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))</ |
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))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 61: | Line 64: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% calculate Recaman's sequence values % |
% calculate Recaman's sequence values % |
||
Line 75: | Line 78: | ||
reference(AValue) array hashTable ( 0 :: HMOD - 1 ); |
reference(AValue) array hashTable ( 0 :: HMOD - 1 ); |
||
integer array A ( 0 :: 14 ); |
integer array A ( 0 :: 14 ); |
||
integer le1000Count, firstN, duplicateN, duplicateValue, n, An, An1, prevN; |
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 % |
% adds an element to the hash table, returns true if an element with value An % |
||
Line 104: | Line 107: | ||
A( 0 ) := An1 := n := 0; |
A( 0 ) := An1 := n := 0; |
||
le1000Count := 0; |
le1000Count := 0; |
||
firstN := duplicateN := duplicateValue := -1; |
maxS := firstN := duplicateN := duplicateValue := -1; |
||
while le1000Count < 1000 do begin |
while le1000Count < 1000 do begin |
||
logical le0, duplicate; |
logical le0, duplicate; |
||
Line 127: | Line 130: | ||
else if An <= 1000 then le1000Count := le1000Count + 1;; |
else if An <= 1000 then le1000Count := le1000Count + 1;; |
||
if n < 15 then A( n ) := An; |
if n < 15 then A( n ) := An; |
||
if An > maxS then maxS := An; |
|||
An1 := An |
An1 := An |
||
end while_le1000Count_lt_1000 ; |
end while_le1000Count_lt_1000 ; |
||
Line 145: | Line 149: | ||
); |
); |
||
% number of elements required to include the first 1000 integers % |
% 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, "first element to include all 1..1000: ", n ); |
||
write( i_w := 1, "max sequence value encountered: ", maxS ) |
|||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 154: | Line 159: | ||
First duplicates: 20 24 (42) |
First duplicates: 20 24 (42) |
||
first element to include all 1..1000: 328002 |
first element to include all 1..1000: 328002 |
||
max sequence value encountered: 1942300 |
|||
</pre> |
</pre> |
||
=={{header|APL}}== |
=={{header|APL}}== |
||
{{works with|Dyalog APL}} |
{{works with|Dyalog APL}} |
||
< |
<syntaxhighlight lang="apl">recaman←{⎕IO←0 |
||
genNext←{ |
genNext←{ |
||
R←⍵[N-1]-N←≢⍵ |
R←⍵[N-1]-N←≢⍵ |
||
Line 170: | Line 176: | ||
⎕←'Length of sequence containing [0..1000]:' |
⎕←'Length of sequence containing [0..1000]:' |
||
⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca |
⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 185: | Line 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. |
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. |
||
< |
<syntaxhighlight lang="applescript">use AppleScript version "2.4" |
||
use framework "Foundation" |
use framework "Foundation" |
||
use scripting additions |
use scripting additions |
||
Line 372: | Line 378: | ||
on unwords(xs) |
on unwords(xs) |
||
intercalateS(space, xs) |
intercalateS(space, xs) |
||
end unwords</ |
end unwords</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First 15 Recamans: |
<pre>First 15 Recamans: |
||
Line 385: | Line 391: | ||
(Last result took c. 40 seconds to find)</pre> |
(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}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f RECAMANS_SEQUENCE.AWK |
# syntax: GAWK -f RECAMANS_SEQUENCE.AWK |
||
# converted from Microsoft Small Basic |
# converted from Microsoft Small Basic |
||
Line 431: | Line 476: | ||
exit(0) |
exit(0) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 440: | Line 485: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
< |
<syntaxhighlight lang="gwbasic">10 DEFINT A-Z: DIM A(100) |
||
20 PRINT "First 15 terms:" |
20 PRINT "First 15 terms:" |
||
30 FOR N=0 TO 14: GOSUB 100: PRINT A(N);: NEXT |
30 FOR N=0 TO 14: GOSUB 100: PRINT A(N);: NEXT |
||
Line 456: | Line 501: | ||
140 NEXT |
140 NEXT |
||
150 A(N)=X: RETURN |
150 A(N)=X: RETURN |
||
160 A(N)=A(N-1)+N: RETURN</ |
160 A(N)=A(N-1)+N: RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 15 terms: |
<pre>First 15 terms: |
||
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
||
First repeated term: |
First repeated term: |
||
A( 24 ) = 42</pre> |
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}}== |
=={{header|C}}== |
||
{{libheader|GLib}} |
{{libheader|GLib}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <gmodule.h> |
#include <gmodule.h> |
||
Line 521: | Line 678: | ||
free(a); |
free(a); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 532: | Line 689: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 570: | Line 727: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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] |
<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: | Line 735: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <ostream> |
#include <ostream> |
||
#include <set> |
#include <set> |
||
Line 634: | Line 791: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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] |
<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 |
The first duplicated term is a[24] = 42 |
||
Terms up to a[328002] are needed to generate 0 to 1000</pre> |
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}}== |
=={{header|D}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
void main() { |
void main() { |
||
Line 680: | Line 1,017: | ||
n++; |
n++; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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] |
<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 |
The first duplicated term is a[24] = 42 |
||
Terms up to a[328002] are needed to generate 0 to 1000</pre> |
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}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 26-01-2019 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 754: | Line 1,200: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 15 terms are 0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
<pre>The first 15 terms are 0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
||
Line 764: | Line 1,210: | ||
=={{header|FOCAL}}== |
=={{header|FOCAL}}== |
||
< |
<syntaxhighlight lang="focal">01.10 T "FIRST 15" |
||
01.20 F N=0,14;D 2;T %2,A(N) |
01.20 F N=0,14;D 2;T %2,A(N) |
||
01.30 T !"FIRST REPEATED" |
01.30 T !"FIRST REPEATED" |
||
Line 782: | Line 1,228: | ||
02.50 I (Y)2.6,2.7,2.6 |
02.50 I (Y)2.6,2.7,2.6 |
||
02.60 S A(N)=X;R |
02.60 S A(N)=X;R |
||
02.70 S A(N)=A(N-1)+N</ |
02.70 S A(N)=A(N-1)+N</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 792: | Line 1,238: | ||
=={{header|Fōrmulæ}}== |
=={{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]] |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition. |
|||
[[File:Fōrmulæ - Recamán's sequence 09.png]] |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 838: | Line 1,312: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 850: | Line 1,324: | ||
===Recursion=== |
===Recursion=== |
||
A basic recursive function for the first N terms, |
A basic recursive function for the first N terms, |
||
< |
<syntaxhighlight lang="haskell">recaman :: Int -> [Int] |
||
recaman n = fst <$> reverse (go n) |
recaman n = fst <$> reverse (go n) |
||
where |
where |
||
Line 865: | Line 1,339: | ||
main :: IO () |
main :: IO () |
||
main = print $ recaman 15</ |
main = print $ recaman 15</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]</pre> |
<pre>[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]</pre> |
||
Line 872: | Line 1,346: | ||
Or, a little more flexibly, a '''recamanUpto''' (predicate) function. |
Or, a little more flexibly, a '''recamanUpto''' (predicate) function. |
||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
< |
<syntaxhighlight lang="haskell">import Data.Set (Set, fromList, insert, isSubsetOf, member, size) |
||
import Data.Bool (bool) |
import Data.Bool (bool) |
||
Line 913: | Line 1,387: | ||
, "Length of Recaman series required to include [0..1000]:" |
, "Length of Recaman series required to include [0..1000]:" |
||
, (show . length . recamanSuperset) $ fromList [0 .. 1000] |
, (show . length . recamanSuperset) $ fromList [0 .. 1000] |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First 15 Recamans: |
<pre>First 15 Recamans: |
||
Line 929: | Line 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. |
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. |
||
< |
<syntaxhighlight lang="haskell">import Data.List (find, findIndex, nub) |
||
import Data.Maybe (fromJust) |
import Data.Maybe (fromJust) |
||
import Data.Set (Set, fromList, insert, isSubsetOf, member) |
import Data.Set (Set, fromList, insert, isSubsetOf, member) |
||
Line 975: | Line 1,449: | ||
"Length of Recaman series required to include [0..1000]:", |
"Length of Recaman series required to include [0..1000]:", |
||
show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets |
show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First 15 Recamans: |
<pre>First 15 Recamans: |
||
Line 1,027: | Line 1,501: | ||
</pre> |
</pre> |
||
Let's write a binary search adverb. |
Let's write a binary search adverb. |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
average =: +/ % # |
average =: +/ % # |
||
NB. extra_data u Bsearch bounds |
NB. extra_data u Bsearch bounds |
||
Line 1,035: | Line 1,509: | ||
NB. u is invoked as a dyad |
NB. u is invoked as a dyad |
||
Bsearch =: 1 :'((0 1 + (u <.@:average)) { ({. , <.@:average, {:)@:])^:_' |
Bsearch =: 1 :'((0 1 + (u <.@:average)) { ({. , <.@:average, {:)@:])^:_' |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
NB. f expresses "not all [0, 1000] are in the first y members of list x" |
NB. f expresses "not all [0, 1000] are in the first y members of list x" |
||
Line 1,054: | Line 1,528: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{Trans|Kotlin}} |
{{Trans|Kotlin}} |
||
< |
<syntaxhighlight lang="java">import java.util.ArrayList; |
||
import java.util.HashSet; |
import java.util.HashSet; |
||
import java.util.List; |
import java.util.List; |
||
Line 1,098: | Line 1,572: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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] |
<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: | Line 1,580: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
const main = () => { |
const main = () => { |
||
Line 1,191: | Line 1,665: | ||
// MAIN ------------------------------------------------ |
// MAIN ------------------------------------------------ |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First 15 Recaman: |
<pre>First 15 Recaman: |
||
Line 1,202: | Line 1,676: | ||
all integers from [0..1000]: |
all integers from [0..1000]: |
||
328002</pre> |
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}}== |
=={{header|Julia}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="julia">function recaman() |
||
a = Vector{Int}([0]) |
a = Vector{Int}([0]) |
||
used = Dict{Int, Bool}(0 => true) |
used = Dict{Int, Bool}(0 => true) |
||
Line 1,235: | Line 1,852: | ||
recaman() |
recaman() |
||
</ |
</syntaxhighlight>{{output}}<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 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. |
The first duplicated term is a[25] = 42. |
||
Line 1,243: | Line 1,860: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="scala">// Version 1.2.60 |
||
fun main(args: Array<String>) { |
fun main(args: Array<String>) { |
||
Line 1,272: | Line 1,889: | ||
n++ |
n++ |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 1,284: | Line 1,901: | ||
This runs out of memory determining the final part :( |
This runs out of memory determining the final part :( |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="lua">local a = {[0]=0} |
||
local used = {[0]=true} |
local used = {[0]=true} |
||
local used1000 = {[0]=true} |
local used1000 = {[0]=true} |
||
Line 1,318: | Line 1,935: | ||
end |
end |
||
n = n + 1 |
n = n + 1 |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{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 |
<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 |
The first duplicated term is a[24] = 42 |
||
lua: not enough memory</pre> |
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}}== |
=={{header|Microsoft Small Basic}}== |
||
Inefficency of associative array allocation in Small Basic ban to provide the optional task. |
Inefficency of associative array allocation in Small Basic ban to provide the optional task. |
||
< |
<syntaxhighlight lang="smallbasic">' Recaman's sequence - smallbasic - 05/08/2015 |
||
nn=15 |
nn=15 |
||
TextWindow.WriteLine("Recaman's sequence for the first " + nn + " numbers:") |
TextWindow.WriteLine("Recaman's sequence for the first " + nn + " numbers:") |
||
Line 1,369: | Line 2,060: | ||
EndFor |
EndFor |
||
exitsub: |
exitsub: |
||
EndSub </ |
EndSub </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,378: | Line 2,069: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import sequtils, sets, strutils |
||
iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] = |
iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] = |
||
Line 1,404: | Line 2,095: | ||
if target.card == 0: |
if target.card == 0: |
||
echo "All numbers from 0 to 1000 generated after $1 terms.".format(n) |
echo "All numbers from 0 to 1000 generated after $1 terms.".format(n) |
||
break</ |
break</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,413: | Line 2,104: | ||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">use Collection.Generic; |
||
class RecamanSequence { |
class RecamanSequence { |
||
Line 1,472: | Line 2,163: | ||
return out; |
return out; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 1,482: | Line 2,173: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use bignum; |
||
$max = 1000; |
$max = 1000; |
||
Line 1,503: | Line 2,194: | ||
print "First fifteen terms of Recaman's sequence: " . join(' ', @recamans[0..14]) . "\n"; |
print "First fifteen terms of Recaman's sequence: " . join(' ', @recamans[0..14]) . "\n"; |
||
print "First duplicate at term: a[$dup]\n"; |
print "First duplicate at term: a[$dup]\n"; |
||
print "Range 0..1000 covered by terms up to a[$term]\n";</ |
print "Range 0..1000 covered by terms up to a[$term]\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
<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: | Line 2,202: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|D}} |
{{trans|D}} |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>bool found_duplicate = false |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
sequence used = {} -- (grows to 1,942,300 entries) |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">found_duplicate</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
integer all_used = 0 |
|||
<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> |
|||
sequence a = {0} |
|||
<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> |
|||
integer n = 1, next, prev = 0 |
|||
<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> |
|||
while n<=15 or not found_duplicate or all_used<1000 do |
|||
<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> |
|||
next = prev - n |
|||
<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> |
|||
if next<1 or (next<=length(used) and used[next]) then |
|||
<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> |
|||
next = prev + n |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">next</span> |
|||
a &= next |
|||
<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> |
|||
integer pad = next-length(used) |
|||
<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> |
|||
bool already_used = pad<=0 and used[next] |
|||
<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> |
|||
if not already_used then |
|||
<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> |
|||
if pad>0 then used &= repeat(false,pad) end if |
|||
<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> |
|||
used[next] = true |
|||
<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> |
|||
while all_used<length(used) and used[all_used+1] do |
|||
<span style="color: #000000;">all_used</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
all_used += 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<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> |
|||
if length(a)=15 then |
|||
<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> |
|||
puts(1,"The first 15 terms of the Recaman sequence are: ") ?a |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<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> |
|||
if already_used and not found_duplicate then |
|||
<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> |
|||
printf(1,"The first duplicated term is a[%d] = %d\n", {n, next}) |
|||
<span style="color: #000000;">found_duplicate</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">;</span> |
|||
found_duplicate = true; |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<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> |
|||
if all_used>=1000 then |
|||
<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> |
|||
printf(1,"Terms up to a[%d] are needed to generate 0 to 1000\n", {n}); |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span> |
|||
prev = next |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
n += 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end while</lang> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,553: | Line 2,245: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="php"><?php |
||
$a = array(); |
$a = array(); |
||
array_push($a, 0); |
array_push($a, 0); |
||
Line 1,598: | Line 2,290: | ||
$n++; |
$n++; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,605: | Line 2,297: | ||
The first duplicate term is a[24] = 42 |
The first duplicate term is a[24] = 42 |
||
Terms up to a[328002] are needed to generate 0 to 1000 |
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}}== |
|||
<syntaxhighlight lang="purebasic">#MAX=500000 |
|||
Dim a.i(#MAX) |
|||
Dim b.b(1) |
|||
Dim c.b(1000) |
|||
FillMemory(@c(),1000,1,#PB_Byte) |
|||
If OpenConsole() : Else : End 1 : EndIf |
|||
For n_Count=0 To #MAX |
|||
If n_Count=0 |
|||
a(n_Count)=0 |
|||
ElseIf a(n_Count-1)-n_Count>0 And b(a(n_Count-1)-n_Count)=0 |
|||
a(n_Count)=a(n_Count-1)-n_Count |
|||
Else |
|||
a(n_Count)=a(n_Count-1)+n_Count |
|||
EndIf |
|||
If ArraySize(b())<a(n_Count) : ReDim b(a(n_Count)) : EndIf |
|||
If b(a(n_Count))=1 And fitD=0 : fitD=n_Count : EndIf |
|||
b(a(n_Count))=1 |
|||
If CompareMemory(@b(),@c(),1000) And fit1000=0 : fit1000=n_Count : Break : EndIf |
|||
Next |
|||
Print("First 15 terms: ") : For i=0 To 14 : Print(RSet(Str(a(i)),4)) : Next : PrintN("") |
|||
PrintN("First duplicate term : a("+Str(fitD)+") = "+Str(a(fitD))) |
|||
PrintN("Number of Recaman terms needed to generate all integers from [0..1000]: "+Str(fit1000)) |
|||
Input() |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
|||
First duplicate term : a(24) = 42 |
|||
Number of Recaman terms needed to generate all integers from [0..1000]: 328002 |
|||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Conditional iteration over a generator=== |
===Conditional iteration over a generator=== |
||
< |
<syntaxhighlight lang="python">from itertools import islice |
||
class Recamans(): |
class Recamans(): |
||
Line 1,650: | Line 2,496: | ||
if setn.issubset(recamans.a): |
if setn.issubset(recamans.a): |
||
print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})") |
print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})") |
||
break</ |
break</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,661: | Line 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()'') |
( 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()'') |
||
< |
<syntaxhighlight lang="python">'''Recaman sequence''' |
||
Line 1,727: | Line 2,573: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First 15 Recaman: |
<pre>First 15 Recaman: |
||
Line 1,743: | Line 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()'' ). |
( 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()'' ). |
||
< |
<syntaxhighlight lang="python">'''Recaman by iteration of a function over a tuple.''' |
||
from itertools import (islice) |
from itertools import (islice) |
||
Line 1,852: | Line 2,698: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
<pre>First 15 Recaman: |
<pre>First 15 Recaman: |
||
[0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9] |
[0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9] |
||
Line 1,859: | Line 2,705: | ||
Number of Recaman terms needed to generate all integers from [0..1000]: |
Number of Recaman terms needed to generate all integers from [0..1000]: |
||
328002</pre> |
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}}== |
=={{header|R}}== |
||
A bit slow because the append() function is expensive. |
A bit slow because the append() function is expensive. |
||
< |
<syntaxhighlight lang="rsplus"> |
||
visited <- vector('logical', 1e8) |
visited <- vector('logical', 1e8) |
||
Line 1,904: | Line 2,811: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,916: | Line 2,823: | ||
{{works with|Rakudo|2018.06}} |
{{works with|Rakudo|2018.06}} |
||
<lang |
<syntaxhighlight lang="raku" line>my @recamans = 0, { |
||
state %seen; |
state %seen; |
||
state $term; |
state $term; |
||
Line 1,936: | Line 2,843: | ||
@seen[$this] = 1; |
@seen[$this] = 1; |
||
say "Range 0..1000 covered by terms up to a[{$i - 1}]" and last if ++$ == 1001; |
say "Range 0..1000 covered by terms up to a[{$i - 1}]" and last if ++$ == 1001; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
<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,952: | Line 2,859: | ||
could've been replaced with: |
could've been replaced with: |
||
if !.z | z<0 then z= _ + # |
if !.z | z<0 then z= _ + # |
||
< |
<syntaxhighlight lang="rexx">/*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*/ |
parse arg N h . /*obtain optional arguments from the CL*/ |
||
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/ |
||
Line 1,977: | Line 2,884: | ||
end |
end |
||
$= $ z /*add number to $ list?*/ |
$= $ z /*add number to $ list?*/ |
||
end /*#*/; return $ /*return the $ list. */</ |
end /*#*/; return $ /*return the $ list. */</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
Line 1,990: | Line 2,897: | ||
===version 2=== |
===version 2=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes & displays the Recaman sequence */ |
||
/*improved using version 1's method for task 3 */ |
/*improved using version 1's method for task 3 */ |
||
Call time 'R' /* Start timer */ |
Call time 'R' /* Start timer */ |
||
Line 2,035: | Line 2,942: | ||
Have.temp=1 |
Have.temp=1 |
||
End |
End |
||
Return s</ |
Return s</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
<pre>the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
||
Line 2,043: | Line 2,950: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "zerolib.ring" |
load "zerolib.ring" |
||
Line 2,093: | Line 3,000: | ||
see "" + dupnr + "] = " + duplicate + nl |
see "" + dupnr + "] = " + duplicate + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,101: | Line 3,008: | ||
the first duplicated term is a[24] = 42 |
the first duplicated term is a[24] = 42 |
||
done... |
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> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="ruby">require 'set' |
||
a = [0] |
a = [0] |
||
Line 2,136: | Line 3,101: | ||
end |
end |
||
n = n + 1 |
n = n + 1 |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{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] |
<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 |
The first duplicated term is a[24] = 42 |
||
Terms up to a[328002] are needed to generate 0 to 1000</pre> |
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}}== |
=={{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)]. |
{{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)]. |
||
< |
<syntaxhighlight lang="scala">import scala.collection.mutable |
||
object RecamansSequence extends App { |
object RecamansSequence extends App { |
||
Line 2,172: | Line 3,173: | ||
println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}") |
println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}") |
||
}</ |
}</syntaxhighlight> |
||
=={{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}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func recamans_generator() { |
||
var term = 0 |
var term = 0 |
||
Line 2,220: | Line 3,345: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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 |
<pre>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 |
First duplicate term in the series is a(24) = 42 |
||
Terms up to a(328002) are needed to generate 0 to 1000</pre> |
Terms up to a(328002) are needed to generate 0 to 1000</pre> |
||
=={{header|uBasic/4tH}}== |
|||
<syntaxhighlight lang="basic">a = 0 ' the first one is free ;-) |
|||
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 Func(_Peek(b)) Then Print "\nFirst repetition: ";b : Break |
|||
Proc _Set(Set(a, b)) ' set bit in bitmap |
|||
Next |
|||
End ' terminate program |
|||
' bitmap functions |
|||
_Set Param(1) : Let @(a@/32) = Func(_Poke(a@/32, a@%32)) : Return |
|||
_Poke Param(2) : Return (Or(@(a@), Shl(1, b@))) |
|||
_Peek Param(1) : Return (And(@(a@/32), Shl(1, a@%32))>0) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 15 numbers: |
|||
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 |
|||
First repetition: 42 |
|||
0 OK, 0:459 |
|||
</pre> |
|||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
{{trans|Rexx}} |
{{trans|Rexx}} |
||
To run in console mode with cscript. |
To run in console mode with cscript. |
||
< |
<syntaxhighlight lang="vb">' Recaman's sequence - vbscript - 04/08/2015 |
||
nx=15 |
nx=15 |
||
h=1000 |
h=1000 |
||
Line 2,286: | Line 3,436: | ||
next 'n |
next 'n |
||
recaman=list |
recaman=list |
||
end function 'recaman</ |
end function 'recaman</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,297: | Line 3,447: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Imports System |
||
Imports System.Collections.Generic |
Imports System.Collections.Generic |
||
Line 2,321: | Line 3,471: | ||
Next |
Next |
||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight>{{out}} |
||
<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) |
<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 |
The first duplicated term is a(24) = 42 |
||
Line 2,328: | Line 3,478: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="wren">var a = [0] |
||
var used = { 0: true } |
var used = { 0: true } |
||
var used1000 = { 0: true } |
var used1000 = { 0: true } |
||
Line 2,351: | Line 3,501: | ||
} |
} |
||
n = n + 1 |
n = n + 1 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,362: | Line 3,512: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn recamanW{ // -->iterator -->(n,a,True if a is a dup) |
||
Walker.tweak(fcn(rn,rp,d){ |
Walker.tweak(fcn(rn,rp,d){ |
||
n,p,a := rn.value, rp.value, p - n; |
n,p,a := rn.value, rp.value, p - n; |
||
Line 2,369: | Line 3,519: | ||
return(rn.inc(),a,d[a]>1); |
return(rn.inc(),a,d[a]>1); |
||
}.fp(Ref(0),Ref(0),Dictionary()) ) |
}.fp(Ref(0),Ref(0),Dictionary()) ) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">print("First 15 members of Recaman's sequence: "); |
||
recamanW().walk(15).apply("get",1).println(); |
recamanW().walk(15).apply("get",1).println(); |
||
Line 2,378: | Line 3,528: | ||
rw,ns,n,a,dup := recamanW(),1000,0,0,0; |
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); |
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));</ |
println("Range 0..1000 is covered by terms up to a(%,d)".fmt(n));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 14:06, 3 April 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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 a(0)=0, the n'th term a(n)
, where n>0, 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 previously generated.
If the conditions don't hold then a(n) = a(n-1) + n
.
- 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, how many terms of the sequence are needed until all the integers 0..1000, inclusive, are generated.
- References
- A005132, The On-Line Encyclopedia of Integer Sequences.
- The Slightly Spooky Recamán Sequence, Numberphile video.
- Recamán's sequence, on Wikipedia.
11l
F recamanSucc(seen, n, r)
‘The successor for a given Recaman term,
given the set of Recaman terms seen so far.’
V back = r - n
R I 0 > back | (back C seen) {n + r} E back
F recamanUntil(p)
‘All terms of the Recaman series before the
first term for which the predicate p holds.’
V n = 1
V r = 0
V rs = [r]
V seen = Set(rs)
V blnNew = 1B
L !p(seen, n, r, blnNew)
r = recamanSucc(seen, n, r)
blnNew = r !C seen
seen.add(r)
rs.append(r)
n = 1 + n
R rs
F enumFromTo(m)
‘Integer enumeration from m to n.’
R n -> @m .< 1 + n
print("First 15 Recaman:\n "recamanUntil((seen, n, r, _) -> n == 15))
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))
- 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
ALGOL W
begin
% calculate Recaman's sequence values %
% a hash table element - holds n, A(n) and a link to the next element with the %
% same hash value %
record AValue ( integer eN, eAn ; reference(AValue) eNext );
% hash modulus %
integer HMOD;
HMOD := 100000;
begin
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 %
% was already present, false otherwise %
% if the value was already present, its eN value is returned in prevN %
logical procedure addAValue( integer value n, An ; integer result prevN ) ;
begin
integer hash;
logical duplicate;
reference(AValue) element;
hash := An rem HMOD;
element := hashTable( hash );
duplicate := false;
while element not = null and eAn(element) not = An do element := eNext(element);
duplicate := element not = null;
if not duplicate then hashTable( hash ) := AValue( n, An, hashTable( hash ) )
else prevN := eN(element);
duplicate
end addAValue ;
% initialise the hash table %
for h := 0 until HMOD - 1 do hashTable( h ) := null;
% calculate the values of the sequence until we have found values that %
% include all numbers in 1..1000 %
% also store the first 15 values %
A( 0 ) := An1 := n := 0;
le1000Count := 0;
maxS := firstN := duplicateN := duplicateValue := -1;
while le1000Count < 1000 do begin
logical le0, duplicate;
n := n + 1;
An := An1 - n;
le0 := ( An <= 0 );
if le0 then An := An1 + n;
prevN := -1;
duplicate := addAValue( n, An, prevN );
if duplicate and not le0 then begin
An := An1 + n;
duplicate := addAValue( n, An, prevN )
end if_duplicate_and_not_le0 ;
if duplicate then begin
% the value was already present %
if firstN < 0 then begin % have the first duplicate %
firstN := n;
duplicateN := prevN;
duplicateValue := An;
end if_firstN_lt_0
end
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 ;
% show the first 15 values of the sequence %
write( "A( 0 .. 14 ): " );
for n := 0 until 14 do writeon( i_w := 1, A( n ) );
% positions of the first duplicate %
write( i_w := 1
, s_w := 0
, "First duplicates: "
, duplicateN
, " "
, firstN
, " ("
, duplicateValue
, ")"
);
% 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.
- Output:
A( 0 .. 14 ): 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First duplicates: 20 24 (42) first element to include all 1..1000: 328002 max sequence value encountered: 1942300
APL
recaman←{⎕IO←0
genNext←{
R←⍵[N-1]-N←≢⍵
(R<0)∨(R∊⍵):⍵,⍵[N-1]+N
⍵,⍵[N-1]-N
}
⎕←'First 15: '
⎕←reca←(genNext⍣14),0
⎕←'First repetition: '
⎕←⊃⌽reca←genNext⍣{⍺≢∪⍺}⊢reca
⎕←'Length of sequence containing [0..1000]:'
⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca
}
- Output:
First 15: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repetition: 42 Length of sequence containing [0..1000]: 328003
AppleScript
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)
Arturo
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]
- Output:
First 15 Recaman numbers: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First duplicate Recaman number: 42
AWK
# syntax: GAWK -f RECAMANS_SEQUENCE.AWK
# converted from Microsoft Small Basic
BEGIN {
found_dup = 0
n = -1
do {
n++
ap = a[n-1] + n
if (a[n-1] <= n) {
a[n] = ap
b[ap] = 1
}
else {
am = a[n-1] - n
if (b[am] == 1) {
a[n] = ap
b[ap] = 1
}
else {
a[n] = am
b[am] = 1
}
}
if (n <= 14) {
terms = sprintf("%s%s ",terms,a[n])
if (n == 14) {
printf("first %d terms: %s\n",n+1,terms)
}
}
if (!found_dup) {
if (dup[a[n]] == 1) {
printf("first duplicated term: a[%d]=%d\n",n,a[n])
found_dup = 1
}
dup[a[n]] = 1
}
if (a[n] <= 1000) {
arr[a[n]] = ""
}
} while (n <= 15 || !found_dup || length(arr) < 1001)
printf("terms needed to generate integers 0 - 1000: %d\n",n)
exit(0)
}
- Output:
first 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 first duplicated term: a[24]=42 terms needed to generate integers 0 - 1000: 328002
BASIC
10 DEFINT A-Z: 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: IF A(M)=A(N) THEN 70 ELSE 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
- Output:
First 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated term: A( 24 ) = 42
Applesoft BASIC
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
Chipmunk Basic
The BASIC solution works without any changes.
GW-BASIC
The BASIC solution works without any changes.
Minimal BASIC
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
MSX Basic
The BASIC solution works without any changes.
Quite BASIC
The Minimal BASIC solution works without any changes.
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)
$)
- Output:
First 15 members: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated term: a!24 = 42
C
#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
C#
using System;
using System.Collections.Generic;
namespace RecamanSequence {
class Program {
static void Main(string[] args) {
List<int> a = new List<int>() { 0 };
HashSet<int> used = new HashSet<int>() { 0 };
HashSet<int> used1000 = new HashSet<int>() { 0 };
bool foundDup = false;
int n = 1;
while (n <= 15 || !foundDup || used1000.Count < 1001) {
int next = a[n - 1] - n;
if (next < 1 || used.Contains(next)) {
next += 2 * n;
}
bool alreadyUsed = used.Contains(next);
a.Add(next);
if (!alreadyUsed) {
used.Add(next);
if (0 <= next && next <= 1000) {
used1000.Add(next);
}
}
if (n == 14) {
Console.WriteLine("The first 15 terms of the Recaman sequence are: [{0}]", string.Join(", ", a));
}
if (!foundDup && alreadyUsed) {
Console.WriteLine("The first duplicated term is a[{0}] = {1}", n, next);
foundDup = true;
}
if (used1000.Count == 1001) {
Console.WriteLine("Terms up to a[{0}] are needed to generate 0 to 1000", n);
}
n++;
}
}
}
}
- Output:
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
C++
#include <iostream>
#include <ostream>
#include <set>
#include <vector>
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
auto i = v.cbegin();
auto e = v.cend();
os << '[';
if (i != e) {
os << *i;
i = std::next(i);
}
while (i != e) {
os << ", " << *i;
i = std::next(i);
}
return os << ']';
}
int main() {
using namespace std;
vector<int> a{ 0 };
set<int> used{ 0 };
set<int> used1000{ 0 };
bool foundDup = false;
int n = 1;
while (n <= 15 || !foundDup || used1000.size() < 1001) {
int next = a[n - 1] - n;
if (next < 1 || used.find(next) != used.end()) {
next += 2 * n;
}
bool alreadyUsed = used.find(next) != used.end();
a.push_back(next);
if (!alreadyUsed) {
used.insert(next);
if (0 <= next && next <= 1000) {
used1000.insert(next);
}
}
if (n == 14) {
cout << "The first 15 terms of the Recaman sequence are: " << a << '\n';
}
if (!foundDup && alreadyUsed) {
cout << "The first duplicated term is a[" << n << "] = " << next << '\n';
foundDup = true;
}
if (used1000.size() == 1001) {
cout << "Terms up to a[" << n << "] are needed to generate 0 to 1000\n";
}
n++;
}
return 0;
}
- Output:
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
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
- Output:
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
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
- Output:
First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated item: A(24) = 42
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.
- Output:
First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated item: A(24) = 42
D
import std.stdio;
void main() {
int[] a;
bool[int] used;
bool[int] used1000;
bool foundDup;
a ~= 0;
used[0] = true;
used1000[0] = true;
int n = 1;
while (n <= 15 || !foundDup || used1000.length < 1001) {
int next = a[n - 1] - n;
if (next < 1 || (next in used) !is null) {
next += 2 * n;
}
bool alreadyUsed = (next in used) !is null;
a ~= next;
if (!alreadyUsed) {
used[next] = true;
if (0 <= next && next <= 1000) {
used1000[next] = true;
}
}
if (n == 14) {
writeln("The first 15 terms of the Recaman sequence are: ", a);
}
if (!foundDup && alreadyUsed) {
writefln("The first duplicated term is a[%d] = %d", n, next);
foundDup = true;
}
if (used1000.length == 1001) {
writefln("Terms up to a[%d] are needed to generate 0 to 1000", n);
}
n++;
}
}
- Output:
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
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
- Output:
First 15 items: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated item: A(24) = 42
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
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
- Output:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 first repeated : a[20 ]=a[24 ]=42 ok
FreeBASIC
' version 26-01-2019
' compile with: fbc -s console
Dim As UByte used()
Dim As Integer sum, temp
Dim As UInteger n, max, count, i
max = 1000 : ReDim used(max)
Print "The first 15 terms are 0";
For n = 0 To 14
temp = sum - n
If temp < 1 OrElse used(temp) = 1 Then
temp = sum + n
End If
If temp <= max Then used(temp) = 1
sum = temp
Print sum;
Next
sum = 0 : max = 1000 : ReDim used(max)
Print : Print
For n = 0 To 50
temp = sum - n
If temp < 1 OrElse used(temp) = 1 Then
temp = sum + n
End If
If used(temp) = 1 Then
Print "First duplicated number is a(" + Str(n) + ")"
Exit For
End If
If temp <= max Then used(temp) = 1
sum = temp
Next
sum = 0 : max = 2000000 : ReDim used(max)
Print : Print
For n = 0 To max
temp = sum - n
If temp < 1 OrElse used(temp) = 1 Then
temp = sum + n
End If
If temp <= max Then used(temp) = 1
If i = temp Then
While used(i) = 1
i += 1
If i > 1000 Then
Exit For
End If
Wend
End If
sum = temp
count += 1
Next
Print "All integers from 0 to 1000 are generated in " & count & " terms"
Print
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
- Output:
The first 15 terms are 0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First duplicated number is a(24) All integers from 0 to 1000 are generated in 328002 terms
FOCAL
01.10 T "FIRST 15"
01.20 F N=0,14;D 2;T %2,A(N)
01.30 T !"FIRST REPEATED"
01.40 D 2;S Y=1
01.50 F M=0,N-1;S Y=Y*(A(M)-A(N))
01.60 I (Y)1.7,1.8,1.7
01.70 S N=N+1;G 1.4
01.80 T A(N)," AT A(",N,")"!
01.90 Q
02.05 I (N)2.1,2.06,2.1
02.06 A(0)=0;R
02.10 S X=A(N-1)-N
02.20 I (X)2.7
02.30 S Y=1
02.40 F M=0,N-1;S Y=Y*(A(M)-X)
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
- Output:
FIRST 15= 0= 1= 3= 6= 2= 7= 13= 20= 12= 21= 11= 22= 10= 23= 9 FIRST REPEATED= 42 AT A(= 24)
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
The following snippet generates the Recaman's sequence of a given number of terms:
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.
Case 2. Plotting the sequence
Case 3. Drawing the sequence as it was shown in the Numberphile video
Go
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
Recursion
A basic recursive function for the first N terms,
recaman :: Int -> [Int]
recaman n = fst <$> reverse (go n)
where
go 0 = []
go 1 = [(0, 1)]
go x =
let xs@((r, i):_) = go (pred x)
back = r - i
in ( if 0 < back && not (any ((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
Or, a little more flexibly, a recamanUpto (predicate) function.
import Data.Set (Set, fromList, insert, isSubsetOf, member, size)
import Data.Bool (bool)
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)
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 bool back (r + i) (0 > back || member back seen)
-- 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
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.List (find, findIndex, nub)
import Data.Maybe (fromJust)
import Data.Set (Set, fromList, insert, isSubsetOf, member)
--- INFINITE STREAM OF RECAMAN SERIES OF GROWING LENGTH --
rSeries :: [[Int]]
rSeries =
scanl
( \rs@(r : _) i ->
let back = r - i
nxt
| 0 > back || elem back rs = r + i
| otherwise = back
in nxt : 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
| 0 > back || member back seen = r + i
| otherwise = 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 ((/=) <$> 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
J
positive =: >&0 unique =: -.@:e. condition =: (positive@:] *. unique~) ({: - #) NB. with the agenda set by the condition, add or subtract tail with tally recaman_term =: ({: + #)`({: - #)@.condition NB. generate four hundred thousand terms and display the first 15 15 {. R=:(, recaman_term)^:400000]0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 NB. plot the sequence to see why numberphile might be interested. load'plot' plot 470{.R NB. binaryish search for first duplicate. (-:&# ~.) 100 {. R 0 (-:&# ~.) 50 {. R 0 (-:&# ~.) 25 {. R 0 (-:&# ~.) 12 {. R 1 (-:&# ~.) 18 {. R 1 (-:&# ~.) 21 {. R 1 (-:&# ~.) 23 {. R 1 (-:&# ~.) 24 {. R 1 (-:&# ~.) 25 {. R 0
Let's write a binary search adverb.
average =: +/ % #
NB. extra_data u Bsearch bounds
NB. Bsearch returns narrowed bounds depending if u return 0 (left) or 1 (right)
NB. u is called as extra_data u index
NB. or as index u index
NB. u is invoked as a dyad
Bsearch =: 1 :'((0 1 + (u <.@:average)) { ({. , <.@:average, {:)@:])^:_'
NB. f expresses "not all [0, 1000] are in the first y members of list x" f =: ([: -. [: *./ (i.1001) e. ~.)@:{.~ R f Bsearch 0 , #R 328002 328003 (<: 328002 328003) { R 328881 879
The sequence begins 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 . With 0 as the first term, We've learned that 25 terms are required to generate a duplicate, and that 328003 terms are needed to generate 0 through 1000 inclusively.
Java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class RecamanSequence {
public static void main(String[] args) {
List<Integer> a = new ArrayList<>();
a.add(0);
Set<Integer> used = new HashSet<>();
used.add(0);
Set<Integer> used1000 = new HashSet<>();
used1000.add(0);
boolean foundDup = false;
int n = 1;
while (n <= 15 || !foundDup || used1000.size() < 1001) {
int next = a.get(n - 1) - n;
if (next < 1 || used.contains(next)) {
next += 2 * n;
}
boolean alreadyUsed = used.contains(next);
a.add(next);
if (!alreadyUsed) {
used.add(next);
if (0 <= next && next <= 1000) {
used1000.add(next);
}
}
if (n == 14) {
System.out.printf("The first 15 terms of the Recaman sequence are : %s\n", a);
}
if (!foundDup && alreadyUsed) {
System.out.printf("The first duplicate term is a[%d] = %d\n", n, next);
foundDup = true;
}
if (used1000.size() == 1001) {
System.out.printf("Terms up to a[%d] are needed to generate 0 to 1000\n", n);
}
n++;
}
}
}
- Output:
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 duplicate term is a[24] = 42 Terms up to a[328002] are needed to generate 0 to 1000
JavaScript
(() => {
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
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
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.
# 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."
- Output:
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.
A stream-oriented solution
# 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) );
The three tasks:
"First 15:", limit(15; recaman),
"\First duplicated:", first(duplicated(recaman)),
"\Index of first element to include 0 to 1000 inclusive:",
(1000|covers(recaman))
- Output:
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
Julia
function recaman()
a = Vector{Int}([0])
used = Dict{Int, Bool}(0 => true)
used1000 = Set(0)
founddup = false
termcount = 1
while length(used1000) <= 1000
nextterm = a[termcount] - termcount
if nextterm < 1 || haskey(used, nextterm)
nextterm += termcount + termcount
end
push!(a, nextterm)
if !haskey(used, nextterm)
used[nextterm] = true
if 1 <= nextterm <= 1000
push!(used1000, nextterm)
end
elseif !founddup
println("The first duplicated term is a[$(termcount + 1)] = $nextterm.")
founddup = true
end
if termcount == 14
println("The first 15 terms of the Recaman sequence are $a")
end
termcount += 1
end
println("Terms up to $(termcount - 1) are needed to generate 0 to 1000.")
end
recaman()
- Output:
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. Terms up to 328002 are needed to generate 0 to 1000.
Kotlin
// 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
Lua
This runs out of memory determining the final part :(
local a = {[0]=0}
local used = {[0]=true}
local used1000 = {[0]=true}
local foundDup = false
local n = 1
while n<=15 or not foundDup or #used1000<1001 do
local nxt = a[n - 1] - n
if nxt<1 or used[nxt] ~= nil then
nxt = nxt + 2 * n
end
local alreadyUsed = used[nxt] ~= nil
table.insert(a, nxt)
if not alreadyUsed then
used[nxt] = true
if 0<=nxt and nxt<=1000 then
used1000[nxt] = true
end
end
if n==14 then
io.write("The first 15 terms of the Recaman sequence are:")
for k=0,#a do
io.write(" "..a[k])
end
print()
end
if not foundDup and alreadyUsed then
print("The first duplicated term is a["..n.."] = "..nxt)
foundDup = true
end
if #used1000 == 1001 then
print("Terms up to a["..n.."] are needed to generate 0 to 1000")
end
n = n + 1
end
- Output:
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
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
- Output:
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
Mathematica / Wolfram Language
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]]
- Output:
{0,1,3,6,2,7,13,20,12,21,11,22,10,23,9} {43,42,79,78} {21,25}
Microsoft Small Basic
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
Nim
import sequtils, sets, strutils
iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] =
var a = 0
yield (0, a, false)
var known = [0].toHashSet
for n in 1..<num:
var next = a - n
if next <= 0 or next in known:
next = a + n
a = next
yield (n, a, a in known)
known.incl a
echo "First 15 numbers in Recaman’s sequence: ", toSeq(recaman(15)).mapIt(it.a).join(" ")
for (n, a, dup) in recaman():
if dup:
echo "First duplicate found: a($1) = $2".format(n, a)
break
var target = toSeq(0..1000).toHashSet
for (n, a, dup) in recaman():
target.excl a
if target.card == 0:
echo "All numbers from 0 to 1000 generated after $1 terms.".format(n)
break
- Output:
First 15 numbers in Recaman’s sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First duplicate found: a(24) = 42 All numbers from 0 to 1000 generated after 328002 terms.
Objeck
use Collection.Generic;
class RecamanSequence {
function : Main(args : String[]) ~ Nil {
GenerateSequence();
}
function : native : GenerateSequence() ~ Nil {
a := Vector->New()<IntHolder>;
a->AddBack(0);
used := Set->New()<IntHolder>;
used->Insert(0);
used1000 := Set->New()<IntHolder>;
used1000->Insert(0);
foundDup := false;
n := 1;
while (n <= 15 | <>foundDup | used1000->Size() < 1001) {
next := a->Get(n - 1) - n;
if (next < 1 | used->Has(next)) {
next += 2 * n;
};
alreadyUsed := used->Has(next);
a->AddBack(next);
if (<>alreadyUsed) {
used->Insert(next);
if (0 <= next & next <= 1000) {
used1000->Insert(next);
};
};
if (n = 14) {
str := ToString(a);
"The first 15 terms of the Recaman sequence are : {$str}"->PrintLine();
};
if (<>foundDup & alreadyUsed) {
"The first duplicate term is a[{$n}] := {$next}"->PrintLine();
foundDup := true;
};
if (used1000->Size() = 1001) {
"Terms up to a[{$n}] are needed to generate 0 to 1000"->PrintLine();
};
n++;
};
}
function : ToString(a : Vector<IntHolder>) ~ String {
out := "[";
each(i : a) {
out += a->Get(i)->Get();
if(i + 1 < a->Size()) {
out += ',';
};
};
out += ']';
return out;
}
}
- Output:
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 duplicate term is a[24] := 42 Terms up to a[328002] are needed to generate 0 to 1000
Perl
use bignum;
$max = 1000;
$remaining += $_ for 1..$max;
my @recamans = 0;
my $previous = 0;
while ($remaining > 0) {
$term++;
my $this = $previous - $term;
$this = $previous + $term unless $this > 0 and !$seen{$this};
push @recamans, $this;
$dup = $term if !$dup and defined $seen{$this};
$remaining -= $this if $this <= $max and ! defined $seen{$this};
$seen{$this}++;
$previous = $this;
}
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";
- 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]
Phix
with javascript_semantics bool found_duplicate = false sequence a = {0}, used = {} -- (grows to 1,942,300 entries) integer all_used = 0, n = 1, next, prev = 0 while n<=15 or not found_duplicate or all_used<1000 do next = prev - n if next<1 or (next<=length(used) and used[next]) then next = prev + n end if a &= next integer padlen = next-length(used) bool already_used = padlen<=0 and used[next] if not already_used then if padlen>0 then used &= repeat(false,padlen) end if used[next] = true while all_used<length(used) and used[all_used+1] do all_used += 1 end while end if if length(a)=15 then printf(1,"The first 15 terms of the Recaman sequence are: %v\n",{a}) end if if already_used and not found_duplicate then printf(1,"The first duplicated term is a[%d] = %d\n", {n, next}) found_duplicate = true; end if if all_used>=1000 then printf(1,"Terms up to a[%d] are needed to generate 0 to 1000\n", {n}); end if prev = next n += 1 end while
- Output:
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
PHP
<?php
$a = array();
array_push($a, 0);
$used = array();
array_push($used, 0);
$used1000 = array();
array_push($used1000, 0);
$foundDup = false;
$n = 1;
while($n <= 15 || !$foundDup || count($used1000) < 1001) {
$next = $a[$n - 1] - $n;
if ($next < 1 || in_array($next, $used)) {
$next += 2 * $n;
}
$alreadyUsed = in_array($next, $used);
array_push($a, $next);
if (!$alreadyUsed) {
array_push($used, $next);
if (0 <= $next && $next <= 1000) {
array_push($used1000, $next);
}
}
if ($n == 14) {
echo "The first 15 terms of the Recaman sequence are : [";
foreach($a as $i => $v) {
if ( $i == count($a) - 1)
echo "$v";
else
echo "$v, ";
}
echo "]\n";
}
if (!$foundDup && $alreadyUsed) {
printf("The first duplicate term is a[%d] = %d\n", $n, $next);
$foundDup = true;
}
if (count($used1000) == 1001) {
printf("Terms up to a[%d] are needed to generate 0 to 1000\n", $n);
}
$n++;
}
- Output:
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 duplicate term is a[24] = 42 Terms up to a[328002] are needed to generate 0 to 1000
PL/I
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;
- Output:
First 15 members: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repeated term: A(24) = 42
PL/M
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
- Output:
FIRST 15 MEMBERS: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 FIRST REPEATED TERM: A(24) = 42
PureBasic
#MAX=500000
Dim a.i(#MAX)
Dim b.b(1)
Dim c.b(1000)
FillMemory(@c(),1000,1,#PB_Byte)
If OpenConsole() : Else : End 1 : EndIf
For n_Count=0 To #MAX
If n_Count=0
a(n_Count)=0
ElseIf a(n_Count-1)-n_Count>0 And b(a(n_Count-1)-n_Count)=0
a(n_Count)=a(n_Count-1)-n_Count
Else
a(n_Count)=a(n_Count-1)+n_Count
EndIf
If ArraySize(b())<a(n_Count) : ReDim b(a(n_Count)) : EndIf
If b(a(n_Count))=1 And fitD=0 : fitD=n_Count : EndIf
b(a(n_Count))=1
If CompareMemory(@b(),@c(),1000) And fit1000=0 : fit1000=n_Count : Break : EndIf
Next
Print("First 15 terms: ") : For i=0 To 14 : Print(RSet(Str(a(i)),4)) : Next : PrintN("")
PrintN("First duplicate term : a("+Str(fitD)+") = "+Str(a(fitD)))
PrintN("Number of Recaman terms needed to generate all integers from [0..1000]: "+Str(fit1000))
Input()
End
- Output:
First 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First duplicate term : a(24) = 42 Number of Recaman terms needed to generate all integers from [0..1000]: 328002
Python
Conditional iteration over a generator
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)
Parameterised query predicates
Passing different query predicates to a single more general function:
( 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())
'''Recaman sequence'''
# recamanUntil :: (Int -> Set Int > [Int] -> Bool) -> [Int]
def recamanUntil(p):
'''All terms of the Recaman series before the
first term for which the predicate p holds.'''
n = 1
r = 0 # First term of series
rs = [r]
seen = set(rs)
blnNew = True
while not p(seen, n, r, blnNew):
r = recamanSucc(seen, n, r)
blnNew = r not in seen
seen.add(r)
rs.append(r)
n = 1 + n
return rs
# recamanSucc :: Set Int -> Int -> Int
def recamanSucc(seen, n, r):
'''The successor for a given Recaman term,
given the set of Recaman terms seen so far.'''
back = r - n
return n + r if 0 > back or (back in seen) else back
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Test'''
print(
'First 15 Recaman:\r',
recamanUntil(
lambda seen, n, r, _: 15 == n
)
)
print(
'First duplicated Recaman:\r',
recamanUntil(
lambda seen, n, r, blnNew: not blnNew
)[-1]
)
setK = set(enumFromTo(0)(1000))
print(
'Number of Recaman terms needed to generate',
'all integers from [0..1000]:\r',
len(recamanUntil(
lambda seen, n, r, blnNew: (
blnNew and 1001 > r and setK.issubset(seen)
)
)) - 1
)
# ----------------------- GENERIC ------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: range(m, 1 + n)
if __name__ == '__main__':
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
Alternatively, we can use query predicates in combination with the iteration of a function over a tuple,
and encapsulate the querying in the generic abstractions iterate and until.
This additional level of abstraction reduces the amount of new code that we have to write, facilitates refactoring, and turns out to have insignificant cost.
( 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() ).
'''Recaman by iteration of a function over a tuple.'''
from itertools import (islice)
# recamanTupleSucc :: Set Int -> (Int, Int, Bool) -> (Int, Int, Bool)
def recamanTupleSucc(seen):
'''The Nth in a series of Recaman tuples,
(N, previous term, boolPreviouslySeen?)
given the set of all terms seen so far.'''
def go(n, r, _):
back = r - n
nxt = n + r if 0 > back or (back in seen) else back
bln = nxt in seen
seen.add(nxt)
return (1 + n, nxt, bln)
return lambda tpl: go(*tpl)
# ------------------------- TEST -------------------------
# main :: IO()
def main():
'''First 15, and first duplicated Recaman.'''
f = recamanTupleSucc(set([0]))
print(
'First 15 Recaman:\n',
list(map(
snd,
take(15)(iterate(f)((1, 0, False)))
))
)
f = recamanTupleSucc(set([0]))
print(
'First duplicated Recaman:\n',
until(lambda x: x[2])(f)(
(1, 0, False)
)[1]
)
sk = set(enumFromTo(0)(1000))
sr = set([0])
f = recamanTupleSucc(sr)
print(
'Number of Recaman terms needed to generate',
'all integers from [0..1000]:\n',
until(
lambda x: not x[2] and 1001 > x[1] and sk.issubset(sr)
)(f)(
(1, 0, False)
)[0] - 1
)
# ----------------- GENERIC ABSTRACTIONS -----------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: range(m, 1 + n)
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated
applications of f to x.
'''
def go(x):
v = x
while True:
yield v
v = f(v)
return go
# snd :: (a, b) -> b
def snd(tpl):
'''Second component of a tuple.'''
return tpl[1]
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else islice(xs, n)
)
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.
'''
def go(f):
def g(x):
v = x
while not p(v):
v = f(v)
return v
return g
return go
# MAIN ---
if __name__ == '__main__':
main()
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
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
- Output:
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
R
A bit slow because the append() function is expensive.
visited <- vector('logical', 1e8)
terms <- vector('numeric')
in_a_interval <- function(v) {
visited[[v+1]]
}
add_value <- function(v) {
visited[[v+1]] <<- TRUE
terms <<- append(terms, v)
}
add_value(0)
step <- 1
value <- 0
founddup <- FALSE
repeat {
if ((value-step>0) && (!in_a_interval(value-step))) {
value <- value - step
} else {
value <- value + step
}
if (in_a_interval(value) && !founddup) {
cat("The first duplicated term is a[",step,"] = ",value,"\n", sep = "")
founddup <- TRUE
}
add_value(value)
if (all(visited[1:1000])) {
cat("Terms up to a[",step,"] are needed to generate 0 to 1000\n",sep = "")
break
}
step <- step + 1
if (step == 15) {
cat("The first 15 terms are :")
for (aterm in terms) { cat(aterm," ", sep = "") }
cat("\n")
}
}
- Output:
The first 15 terms 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
Raku
(formerly Perl 6)
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]
REXX
version 1
Instead of using a subroutine to perform the three tasks with one invocation, the subroutine was used three times
(once for each of the task's three requirements).
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 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
recaman: procedure; parse arg y,,d.; $=0; !.=0; _=0; !.0=1 /*init. array and vars.*/
r= y<0; Reca= 0; hi= abs(y) /*for the 2nd invoke. */
o= y==0; if y<1 then y= 1e8 /* " " 3rd " */
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= 1; _= z /*mark it; add to seq.*/
if r then do; if z>hi then iterate /*ignore #'s too large.*/
if d.z=='' then Reca= Reca + 1 /*Unique? Bump counter.*/
d.z= . /*mark # as a new low. */
if Reca>=hi then return # /*list is complete ≥ HI*/
iterate
end /* [↑] a range of #s. */
if o then do; if d.z==. then return z; d.z=.; iterate /*check if dup #.*/
end
$= $ z /*add number to $ list?*/
end /*#*/; return $ /*return the $ list. */
- output when using the default input:
Run time was about 1/6 of a second, which is over 230% times faster than version 2.
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
/*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
Ring
load "zerolib.ring"
recaman = Z(0:50)
duplicate = 0
dup = []
recDuplicate = []
recnum = 0
see "working..." + nl
see "the first 15 Recaman's numbers are:" + nl
for n = 1 to len(recaman) - 1
if n = 1
recaman[0] = 0
add(dup,0)
see "" + recaman[0] + " "
ok
recaman[n] = recaman[n-1] - n
if recaman[n] <= 0
recaman[n] = recaman[n-1] + n
ok
fnrec = find(dup,recaman[n])
if fnrec > 0
del(dup,fnrec)
recaman[n] = recaman[n-1] + n
add(dup,recaman[n])
else
add(dup,recaman[n])
ok
recnum = recnum + 1
if recnum < 15
see "" + recaman[n] + " "
ok
add(recDuplicate,recaman[n])
next
see nl
see "the first duplicated term is a["
for n = len(recDuplicate) to 2 step -1
for m = n-1 to 1 step -1
if recDuplicate[n] = recDuplicate[m]
duplicate = recDuplicate[n]
dupnr = n
ok
next
next
see "" + dupnr + "] = " + duplicate + nl
see "done..." + nl
- Output:
working... the first 15 Recaman's numbers are: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 the first duplicated term is a[24] = 42 done...
RPL
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 . |
- Input:
{ 0 } 'RKMSQ’ STO 15 RECAM RKMSQ { 0 } ‘RKMSQ’ STO TASK2
- Output:
3: 24 2: { 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 } 1: 42
Ruby
require 'set'
a = [0]
used = Set[0]
used1000 = Set[0]
foundDup = false
n = 1
while n <= 15 or not foundDup or used1000.size < 1001
nxt = a[n - 1] - n
if nxt < 1 or used === nxt then
nxt = nxt + 2 * n
end
alreadyUsed = used === nxt
a << nxt
if not alreadyUsed then
used << nxt
if nxt >= 0 and nxt <= 1000 then
used1000 << nxt
end
end
if n == 14 then
print "The first 15 terms of the Recaman's sequence are ", a, "\n"
end
if not foundDup and alreadyUsed then
print "The first duplicated term is a[", n, "] = ", nxt, "\n"
foundDup = true
end
if used1000.size == 1001 then
print "Terms up to a[", n, "] are needed to generate 0 to 1000\n"
end
n = n + 1
end
- 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
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) ;
}
- Output:
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
Scala
- Output:
Best seen in running your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM).
import scala.collection.mutable
object RecamansSequence extends App {
val (a, used) = (mutable.ArrayBuffer[Int](0), mutable.BitSet())
var (foundDup, hop, nUsed1000) = (false, 1, 0)
while (nUsed1000 < 1000) {
val _next = a(hop - 1) - hop
val next = if (_next < 1 || used.contains(_next)) _next + 2 * hop else _next
val alreadyUsed = used.contains(next)
a += next
if (!alreadyUsed) {
used.add(next)
if (next <= 1000) nUsed1000 += 1
}
if (!foundDup && alreadyUsed) {
println(s"The first duplicate term is a($hop) = $next")
foundDup = true
}
if (nUsed1000 == 1000)
println(s"Terms up to $hop are needed to generate 0 to 1000")
hop += 1
}
println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}")
}
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))
- Output:
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
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;
- Output:
First 15: [0 1 3 6 2 7 13 20 12 21 11 22 10 23 9] First repetition: 42 at {20 24}
Sidef
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
uBasic/4tH
a = 0 ' the first one is free ;-)
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 Func(_Peek(b)) Then Print "\nFirst repetition: ";b : Break
Proc _Set(Set(a, b)) ' set bit in bitmap
Next
End ' terminate program
' bitmap functions
_Set Param(1) : Let @(a@/32) = Func(_Poke(a@/32, a@%32)) : Return
_Poke Param(2) : Return (Or(@(a@), Shl(1, b@)))
_Peek Param(1) : Return (And(@(a@/32), Shl(1, a@%32))>0)
- Output:
First 15 numbers: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 First repetition: 42 0 OK, 0:459
VBScript
To run in console mode with cscript.
' Recaman's sequence - vbscript - 04/08/2015
nx=15
h=1000
Wscript.StdOut.WriteLine "Recaman's sequence for the first " & nx & " numbers:"
Wscript.StdOut.WriteLine recaman("seq",nx)
Wscript.StdOut.WriteLine "The first duplicate number is: " & recaman("firstdup",0)
Wscript.StdOut.WriteLine "The number of terms to complete the range 0--->"& h &" is: "& recaman("numterm",h)
Wscript.StdOut.Write vbCrlf&".../...": zz=Wscript.StdIn.ReadLine()
function recaman(op,nn)
Dim b,d,h
Set b = CreateObject("Scripting.Dictionary")
Set d = CreateObject("Scripting.Dictionary")
list="0" : firstdup=0
if op="firstdup" then
nn=1000 : firstdup=1
end if
if op="numterm" then
h=nn : nn=10000000 : numterm=1
end if
ax=0 'a(0)=0
b.Add 0,1 'b(0)=1
s=0
for n=1 to nn-1
an=ax-n
if an<=0 then
an=ax+n
elseif b.Exists(an) then
an=ax+n
end if
ax=an 'a(n)=an
if not b.Exists(an) then b.Add an,1 'b(an)=1
if op="seq" then
list=list&" "&an
end if
if firstdup then
if d.Exists(an) then
recaman="a("&n&")="&an
exit function
else
d.Add an,1 'd(an)=1
end if
end if
if numterm then
if an<=h then
if not d.Exists(an) then
s=s+1
d.Add an,1 'd(an)=1
end if
if s>=h then
recaman=n
exit function
end if
end if
end if
next 'n
recaman=list
end function 'recaman
- 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 duplicate number is: a(24)=42 The number of terms to complete the range 0--->1000 is: 328002
Visual Basic .NET
Imports System
Imports System.Collections.Generic
Module Module1
Sub Main(ByVal args As String())
Dim a As List(Of Integer) = New List(Of Integer)() From { 0 },
used As HashSet(Of Integer) = New HashSet(Of Integer)() From { 0 },
used1000 As HashSet(Of Integer) = used.ToHashSet(),
foundDup As Boolean = False
For n As Integer = 1 to Integer.MaxValue
Dim nv As Integer = a(n - 1) - n
If nv < 1 OrElse used.Contains(nv) Then nv += 2 * n
Dim alreadyUsed As Boolean = used.Contains(nv) : a.Add(nv)
If Not alreadyUsed Then used.Add(nv) : If nv > 0 AndAlso nv <= 1000 Then used1000.Add(nv)
If Not foundDup Then
If a.Count = 15 Then _
Console.WriteLine("The first 15 terms of the Recamán sequence are: ({0})", String.Join(", ", a))
If alreadyUsed Then _
Console.WriteLine("The first duplicated term is a({0}) = {1}", n, nv) : foundDup = True
End If
If used1000.Count = 1001 Then _
Console.WriteLine("Terms up to a({0}) are needed to generate 0 to 1000", n) : Exit For
Next
End Sub
End Module
- Output:
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 Terms up to a(328002) are needed to generate 0 to 1000
Wren
var a = [0]
var used = { 0: true }
var used1000 = { 0: true }
var foundDup = false
var n = 1
while (n <= 15 || !foundDup || used1000.count < 1001) {
var next = a[n-1] - n
if (next < 1 || used[next]) next = next + 2*n
var alreadyUsed = used[next]
a.add(next)
if (!alreadyUsed) {
used[next] = true
if (next >= 0 && next <= 1000) used1000[next] = true
}
if (n == 14) System.print("The first 15 terms of the Recaman's sequence are:\n%(a)")
if (!foundDup && alreadyUsed) {
System.print("The first duplicated term is a[%(n)] = %(next)")
foundDup = true
}
if (used1000.count == 1001) {
System.print("Terms up to a[%(n)] are needed to generate 0 to 1000")
}
n = n + 1
}
- 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
zkl
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)
- Programming Tasks
- Solutions by Programming Task
- 11l
- ALGOL W
- APL
- AppleScript
- Arturo
- AWK
- BASIC
- Applesoft BASIC
- Chipmunk Basic
- GW-BASIC
- Minimal BASIC
- MSX Basic
- Quite BASIC
- BCPL
- C
- GLib
- C sharp
- C++
- CLU
- Comal
- COBOL
- D
- Draco
- EasyLang
- Forth
- FreeBASIC
- FOCAL
- Fōrmulæ
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- MAD
- Mathematica
- Wolfram Language
- Microsoft Small Basic
- Nim
- Objeck
- Perl
- Phix
- PHP
- PL/I
- PL/M
- PureBasic
- Python
- Quackery
- R
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Scheme
- SETL
- Sidef
- UBasic/4tH
- VBScript
- Visual Basic .NET
- Wren
- Zkl