Recaman's sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Python}}: Or, passing different query predicates to a generalised function)
(→‎{{header|Python}}: Ver 3: querying the iteration of a function over a tuple)
Line 964: Line 964:


=={{header|Python}}==
=={{header|Python}}==
===Conditional iteration over a generator===
<lang python>from itertools import islice
<lang python>from itertools import islice


Line 1,012: Line 1,013:
Range 0 ..1000 is covered by terms up to a(328002)</pre>
Range 0 ..1000 is covered by terms up to a(328002)</pre>


===Parameterised query predicates===

Or, passing different query predicates to a single more general function:
Passing different query predicates to a single more general function:
<lang python># main :: IO ()
<lang python># main :: IO ()
def main():
def main():
Line 1,065: Line 1,066:
main()</lang>
main()</lang>
{{Out}}
{{Out}}
<pre>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</pre>

Alternatively, we can expose more information and allow for richer query predicates by using an iteration of a function over a tuple. This happens to enable the fastest of the three drafts here, letting us to reduce the number of subset tests in the final part of the task. Further optimisations could probably be found if speed became sufficiently valuable or interesting:

<lang python>from itertools import (islice)


# recaman :: Set Int -> (Int, Int, Bool) -> (Int, Int, Bool)
def recaman(seen):
def go(n, r, blnSeen):
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)


def main():
f = recaman(set([0]))
print(
'First 15 Recaman:\n',
_map(lambda x: x[1])(
take(15)(
iterate(f)(
(1, 0, False)
)
)
)
)
f = recaman(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 = recaman(sr)
print(
'Number of Recaman terms needed to generate',
'all integers from [0..1000]:\n',
until(lambda x: not x[2] and sk.issubset(sr))(f)(
(1, 0, False)
)[0]-1
)


# GENERIC ABSTRACTIONS ------------------------------------


# enumFromTo :: Int -> Int -> [Int]
def enumFromTo(m):
return lambda n: list(range(m, 1 + n))


# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
def go(x):
v = x
while True:
yield(v)
v = f(v)
return lambda x: go(x)


# map :: (a -> b) -> [a] -> [b]
def _map(f):
return lambda xs: list(map(f, xs))


# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)


# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)


# MAIN ---
main()</lang>
<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]

Revision as of 15:23, 13 October 2018

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

The Recamán's sequence generates Natural numbers.
Starting from zero, the n'th term a(n) is the previous term minus n i.e a(n) = a(n-1) - n but only if this is both positive and has not been previousely generated.

If the conditions don't hold then a(n) = a(n-1) + n.

Task
  1. Generate and show here the first 15 members of the sequence.
  2. Find and show here, the first duplicated number in the sequence.
  3. Optionally: Find and show here, How many terms of the sequence are needed until all the integers 0..1000, inclusive, are generated.


References



ALGOL W

<lang algolw>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;

       % 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;
       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;
           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 )
   end

end.</lang>

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

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.

<lang applescript>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</lang>

Output:
First 15 Recamans:
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

First duplicated Recaman:
42

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

(Last result took c. 40 seconds to find)

C

Library: GLib
Translation of: Go

<lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. 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;

}</lang>

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#

Translation of: Kotlin

<lang csharp>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++;
           }
       }
   }

}</lang>

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

D

Translation of: Kotlin

<lang 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++;
   }

}</lang>

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

Go

<lang 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)
       }
   }

}</lang>

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, <lang haskell>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</lang>

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.

Translation of: JavaScript

<lang haskell>import Data.Set (Set, fromList, insert, isSubsetOf, member, size)

recamanUpto :: (([Int], Int, Set Int) -> Bool) -> [Int] recamanUpto p = rs 

 where
   (rs, _, _) =
     until
       p
       (\(rs@(r:_), i, seen) ->
           let n = nextR seen i r
           in (n : rs, succ i, insert n seen))
       ([0], 1, fromList [0])

nextR :: Set Int -> Int -> Int -> Int nextR seen i r = 

 let back = r - i
 in if 0 > back || member back seen
      then r + i
      else back

firstNRecamans :: Int -> [Int] firstNRecamans n = reverse $ recamanUpto (\(_, i, _) -> n == i)

firstDuplicateR :: Int firstDuplicateR = head $ recamanUpto (\(rs, _, set) -> size set /= length rs)

recamanSuperset :: Set Int -> [Int] recamanSuperset setInts = 

 tail $ recamanUpto (\(_, _, setR) -> isSubsetOf setInts setR)

-- TEST --------------------------------------------------------------- main :: IO () main = 

 (putStrLn . unlines)
   [ "First 15 Recamans:"
   , show $ firstNRecamans 15
   , []
   , "First duplicated Recaman:"
   , show firstDuplicateR
   , []
   , "Length of Recaman series required to include [0..1000]:"
   , (show . length . recamanSuperset) $ fromList [0 .. 1000]
   ]</lang>
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.

<lang haskell>import Data.Set (Set, fromList, insert, isSubsetOf, member) import Data.List (find, findIndex, nub) import Control.Applicative (liftA2) import Data.Maybe (fromJust)

-- Infinite stream of Recaman series of growing length rSeries :: Int rSeries = 

 scanl
   (\rs@(r:_) i ->
       (let back = r - i
        in (if (0 > back) || elem back rs
              then r + i
              else back) :
           rs))
   [0]
   [1 ..]

-- Infinite stream of Recaman-generated integer sets, of growing size rSets :: [(Set Int, Int)] rSets = 

 scanl
   (\(seen, r) i ->
       (let back = r - i
            nxt =
              if (0 > back) || member back seen
                then r + i
                else back
        in (insert nxt seen, nxt)))
   (fromList [0], 0)
   [1 ..]

-- TEST --------------------------------------------------------------- main :: IO () main = do 

 let setK = fromList [0 .. 1000]
 (putStrLn . unlines)
   [ "First 15 Recamans:"
   , show . reverse . fromJust $ find ((15 ==) . length) rSeries
   , []
   , "First duplicated Recaman:"
   , show . head . fromJust $ find (liftA2 (/=) length (length . nub)) rSeries
   , []
   , "Length of Recaman series required to include [0..1000]:"
   , show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets
   ]</lang>
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

Java

Translation of: Kotlin

<lang 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++;
       }
   }

}</lang>

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

Translation of: Haskell

<lang 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();

})();</lang>

Output:
First 15 Recaman:
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9

First duplicated Recaman:
42

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

Kotlin

Translation of: Go

<lang scala>// 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++
   }

}</lang>

Output:
The first 15 terms of the Recaman's sequence are: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]
The first duplicated term is a[24] = 42
Terms up to a[328002] are needed to generate 0 to 1000

Microsoft Small Basic

Inefficency of associative array allocation in Small Basic ban to provide the optional task. <lang smallbasic>' 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 </lang>

Output:
Recaman's sequence for the first 15 numbers:
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9
The first duplicated term is a[24]=42

Perl

<lang 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";</lang>

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]

Perl 6

Works with: Rakudo version 2018.06

<lang perl6>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;

}</lang>

Output:
First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicate at term: a[24]
Range 0..1000 covered by terms up to a[328002]

Python

Conditional iteration over a generator

<lang python>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</lang>
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: <lang python># main :: IO () def main(): 

   print(
       'First 15 Recaman:\n',
       recamanUpto(
           lambda i, seen, rs: 15 == i
       )
   )
   print (
       'First duplicated Recaman:\n',
       recamanUpto(
           lambda _, rSet, rs: len(rSet) != len(rs)
       )[-1]
   )
   setK = set(enumFromTo(0)(1000))
   print(
       'Number of Recaman terms needed to generate',
       'all integers from [0..1000]:\n',
       len(recamanUpto(
           lambda _, setR, x: setK.issubset(setR)
       )) - 1
   )


  1. recamanUpto :: (Int -> Set Int > [Int] -> Bool) -> [Int]

def recamanUpto(p): 

   i = 1
   r = 0  # First term of series
   rs = [r]
   seen = set(rs)
   while (not p(i, seen, rs)):
       r = nextRecaman(seen, i, r)
       seen.add(r)
       rs.append(r)
       i = 1 + i
   return rs


  1. nextRecaman :: Set Int -> Int -> Int

def nextRecaman(seen, i, n): 

   back = n - i
   return i + n if 0 > back or (back in seen) else back


  1. enumFromTo :: Int -> Int -> [Int]

def enumFromTo(m): 

   return lambda n: list(range(m, 1 + n))


main()</lang>

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 expose more information and allow for richer query predicates by using an iteration of a function over a tuple. This happens to enable the fastest of the three drafts here, letting us to reduce the number of subset tests in the final part of the task. Further optimisations could probably be found if speed became sufficiently valuable or interesting:

<lang python>from itertools import (islice)


  1. recaman :: Set Int -> (Int, Int, Bool) -> (Int, Int, Bool)

def recaman(seen): 

   def go(n, r, blnSeen):
       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)


def main(): 

   f = recaman(set([0]))
   print(
       'First 15 Recaman:\n',
       _map(lambda x: x[1])(
           take(15)(
               iterate(f)(
                   (1, 0, False)
               )
           )
       )
   )
   f = recaman(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 = recaman(sr)
   print(
       'Number of Recaman terms needed to generate',
       'all integers from [0..1000]:\n',
       until(lambda x: not x[2] and sk.issubset(sr))(f)(
           (1, 0, False)
       )[0]-1
   )


  1. GENERIC ABSTRACTIONS ------------------------------------


  1. enumFromTo :: Int -> Int -> [Int]

def enumFromTo(m): 

   return lambda n: list(range(m, 1 + n))


  1. iterate :: (a -> a) -> a -> Gen [a]

def iterate(f): 

   def go(x):
       v = x
       while True:
           yield(v)
           v = f(v)
   return lambda x: go(x)


  1. map :: (a -> b) -> [a] -> [b]

def _map(f): 

   return lambda xs: list(map(f, xs))


  1. take :: Int -> [a] -> [a]
  2. take :: Int -> String -> String

def take(n): 

   return lambda xs: (
       xs[0:n]
       if isinstance(xs, list)
       else list(islice(xs, n))
   )


  1. until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p): 

   def go(f, x):
       v = x
       while not p(v):
           v = f(v)
       return v
   return lambda f: lambda x: go(f, x)


  1. MAIN ---

main()</lang> 

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

REXX

version 1

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

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

could've been replaced with: 

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

<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*/ if N== | N=="," then N= 15 /*Not specified? Then use the default.*/ if h== | h=="," then h= 1000 /* " " " " " " */ 

     say "Recamán's sequence for the first "        N         " numbers: "    recaman(N)

say; say "The first duplicate number in the Recamán's sequence is: " recaman(0) say; say "The number of terms to complete the range 0───►"h ' is: ' recaman(-h) exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ recaman: procedure; arg y,,d.; $=0;  !.= 0;  !.0= 1 /*init. array and vars.*/ 

        r= y<0;    u= y=0;           hi= abs(y)                 /*for the 2nd invoke.  */
        p= y>0;    _= 0;             if y<1  then y= 1e8        /* "   "  3rd    "     */
        s=0                                                     /*# of Recamán #s found*/
           do #=1  for y-1;          z= _ - #                   /*next # might be < 0. */
           if z<0  then              z= _ + #                   /*this is faster than: */
                   else if !.z  then z= _ + #                   /*if !.z | z<0 then ···*/
           _=z;            !.z= 1                               /*add to seq;  mark it.*/
           if p  then $= $ z                                    /*add number to $ list?*/
           if r  then do;  if z>hi     then iterate #           /*ignore #'s too large.*/
                           if d.z==  then s= s + 1            /*This number unique ? */
                           d.z= .                               /*mark # as a new low #*/
                           if s>=hi    then return #            /*list is complete ≤ HI*/
                      end                                       /* [↑]  a range of #s. */
           if u  then do; if d.z==.  then return z; d.z=.; end  /*check if duplicate #.*/
           end   /*#*/
        return $                                                /*return the  $  list. */</lang>
output   when using the default input:
Recamán's sequence for the first  15  numbers:  0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

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

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

version 2

<lang rexx>/*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</lang>

Output:
the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9
First duplicate (42) added in iteration 24 elapsed: 0 seconds
Element number 328002 is the last to satisfy task 3. It is 879
7.126000 seconds elapsed

Sidef

<lang ruby>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
       }
   }

}</lang>

Output:
First 15 terms of the Recaman's sequence: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9
First duplicate term in the series is a(24) = 42
Terms up to a(328002) are needed to generate 0 to 1000

zkl

<lang 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()) )

}</lang> <lang zkl>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));</lang>

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)
Retrieved from "https://rosettacode.org/wiki/Recaman%27s_sequence?oldid=283708"