Recaman's sequence

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

• A005132, The On-Line Encyclopedia of Integer Sequences.
• The Slightly Spooky Recamán Sequence, Numberphile video.

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 ...\n\t"
   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 NSMUTABLE SET ------------------------------------- 
   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 ------------------------------------------------------------

-- https://github.com/RobTrew/prelude-applescript

-- 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

Translation of: Go

<lang c>#include <stdio.h>

1. include <stdlib.h>

1. define TRUE 1
2. define FALSE 0

typedef int bool;

bool used[1001];

bool contains(int a[], int b, int len) {

   int i;
   for (i = 0; i < len; ++i) {
       if (a[i] == b) return TRUE;
   }
   return FALSE;

}

int firstFalse(int start) {

   int i;
   for (i = start; i <= 1000; ++i) {
       if (!used[i]) return i;
   }
   return -1;

}

void init() {

   int i;
   used[0] = TRUE;
   for (i = 1; i <= 1000; ++i) used[i] = FALSE;

}

int main() {

   int i, n, k = 0, next, *a;
   bool foundDup = FALSE;
   init();
   a = malloc(400000 * sizeof(int));
   a[0] = 0;
   for (n = 1; n <= 15 || !foundDup || k != -1; ++n) {
       next = a[n - 1] - n;
       if (next < 1 || contains(a, next, n)) {
           next += 2 * n;
       }
       a[n] = next;
       if (next >= 0 && next <= 1000) used[next] = TRUE;
       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 && contains(a, next, n)) {
           printf("The first duplicated term is a[%d] = %d\n", n, next);
           foundDup = TRUE;
       }
       k = firstFalse(k);
       if (k == -1) {
           printf("Terms up to a[%d] are needed to generate 0 to 1000\n", n);
       }
   }
   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

Go

<lang go>package main

import "fmt"

func contains(a []int, b int) bool {

   for _, j := range a {
       if j == b {
           return true
       }
   }
   return false

}

func main() {

   a := []int{0}
   used := make(map[int]bool, 1001)
   used[0] = true
   for n, foundDup := 1, false; n <= 15 || !foundDup || len(used) < 1001; n++ {
       next := a[n-1] - n
       if next < 1 || contains(a, next) {
           next += 2 * n
       }
       a = append(a, next)
       if next >= 0 && next <= 1000 {
           used[next] = true
       }
       if n == 14 {
           fmt.Println("The first 15 terms of the Recaman's sequence are:", a)
       }
       if !foundDup && contains(a[:n], next) {
           fmt.Printf("The first duplicated term is a[%d] = %d\n", n, next)
           foundDup = true
       }
       if len(used) == 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

A basic recursive function for the first N terms, <lang haskell>import Data.List (find) import Data.Maybe (isNothing)

recaman :: Int -> [Int] recaman n = fst <$> reverse (go n)

 where
   go x
     | 1 > x = []
     | 1 == x = [(0, 1)]
     | otherwise =
       let xs@((r, i):_) = go (pred x)
           back = r - i
       in ( if 0 < back && isNothing (find ((back ==) . fst) xs)
              then back
              else r + i
          , succ i) :
          xs

main :: IO () main = print $ recaman 15</lang>

Output:

[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9]

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

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)
   var foundDup = false
   var n = 1
   while (n <= 15 || !foundDup || used.size < 1001) {
       var next = a[n - 1] - n
       if (next < 1 || a.contains(next)) next += 2 * n
       a.add(next)
       if (next in 0..1000) used.add(next)
       if (n == 14) {
           println("The first 15 terms of the Recaman's sequence are: $a")
       }
       if (!foundDup && a.subList(0, n).contains(next)) {
           println("The first duplicated term is a[$n] = $next")
           foundDup = true
       }
       if (used.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

<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 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 int @seen = 0 xx 1001; 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 sum(@seen) == 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

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

REXX

version 1

<lang rexx>/*REXX program computes & displays the Recaman sequence (also known as Recamán sequence)*/ parse arg N h . /*obtain optional arguments from the CL*/ if N== | N=="," then N= 15 /*Not specified? Then use the default.*/ say "Recamán's sequence for the first " N " numbers:" say recaman(N) say say "The first duplicate number in the Recamán's sequence is: " recaman(0) exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ recaman: procedure; parse arg y 1 oy,,$ !. d.; u=0 /*U: a unique flag. */

        if y==0  then do;  y=1e8;  u=1;  end                     /*for duplicate stuff.*/
        @.=0                                                     /*initialize  @  array*/
             do j=0  for y;      jm=j-1;    p=@.jm
             _=p+j
             if p<=j  then do;   @.j=_;     !._=.;    end        /*for pository values.*/
                      else do;   m=p-j
                           @.j=m                                 /*for negatory values.*/
                           if !.m==.  then do;   @.j=_;   !._=.  /*was defined before? */
                                           end
                           end
             z=@.j                                               /*get the  @.J  value.*/
             if u  then do;   if d.z==.  then return z;   d.z=.;   iterate  /*j*/;    end
             $=$  z                                              /*append  Z  to list. */
             end   /*j*/
        return strip($)                                          /*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

version 2

<lang rexx>/*REXX program computes & displays the Recaman sequence */ Parse Arg n If n= Then n=15 Say recaman(n) 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 shown */ list='0' /* Unique elements so far */ done=0 /* turn on first duplicate switch */ Call time 'R' /* Start timer */ Do i=1 By 1 /* 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 & wordpos(temp,list)=0 Then Do
   list=list temp             /* add to the long list            */
   wn=words(list)             /* number of integers in long list */
   Select                     /* Show some timing information    */
     When wn//100=0 Then
       Say format(temp,4) 'added in iteration' format(i,6),
          'elapsed:' time('E') 'seconds - Element' wn
     When wn>996 Then Do
       Say format(temp,4) 'added in iteration' format(i,6),
          'elapsed:' time('E') 'seconds - Element' wn
       If wn=1001 Then        /* all itegers in long list        */
         Leave
       End
     Otherwise Nop
     End
   End
 If done=0 & have.temp=1 Then Do
   Say 'First duplicate ('temp') added in iteration' i,
      'elapsed:' time('E') 'seconds'
   done=1
   End
 Have.temp=1
 End

Return s</lang>

Output:

I:\>rexx recpa 25
First duplicate (42) added in iteration 24 elapsed: 0 seconds
 370 added in iteration    108 elapsed: 0.016000 seconds - Element 100
 490 added in iteration    232 elapsed: 0.016000 seconds - Element 200
 103 added in iteration    381 elapsed: 0.016000 seconds - Element 300
 338 added in iteration    572 elapsed: 0.016000 seconds - Element 400
 962 added in iteration    675 elapsed: 0.016000 seconds - Element 500
 737 added in iteration    957 elapsed: 0.031000 seconds - Element 600
 529 added in iteration   1201 elapsed: 0.031000 seconds - Element 700
 682 added in iteration   2260 elapsed: 0.069000 seconds - Element 800
 983 added in iteration   4453 elapsed: 0.116000 seconds - Element 900
 223 added in iteration 181545 elapsed: 5.449000 seconds - Element 997
 133 added in iteration 181605 elapsed: 5.452000 seconds - Element 998
  76 added in iteration 181643 elapsed: 5.453000 seconds - Element 999
  61 added in iteration 181653 elapsed: 5.453000 seconds - Element 1000
 879 added in iteration 328002 elapsed: 9.884000 seconds - Element 1001
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42

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)