Recaman's sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(Promote to full task status.)
Line 193: Line 193:
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
Terms up to a[328002] are needed to generate 0 to 1000
</pre>

=={{header|Microsoft Small Basic}}==
<lang smallbasic>
' Recaman's sequence - vbscript - 04/08/2015
n=15
TextWindow.WriteLine("Recaman's sequence for the first " + n + " numbers:")
recaman()
TextWindow.WriteLine(Text.GetSubTextToEnd(recaman,2))
n="firstdup"
recaman()
TextWindow.WriteLine("The first duplicate number in the Recaman's sequence is: " +firstdup)
Sub recaman
recaman=""
firstdup=""
If n="firstdup" Then
n=1000
firstdup="True"
EndIf
For i=0 To n-1
p=ta[i-1]
k=p+i
If p<=i Then
ta[i]=k
tb[k]=1
Else
m=p-i
ta[i]=m
If tb[m]=1 Then
ta[i]=k
tb[k]=1
EndIf
EndIf
j=ta[i]
If firstdup Then
If dup[j]=1 Then
firstdup=j
Goto exitsub
EndIf
dup[j]=1
EndIf
recaman=recaman+","+j
EndFor
exitsub:
EndSub
</lang>
{{out}}
<pre>
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 in the Recaman's sequence is: 42
</pre>
</pre>


Revision as of 23:24, 4 August 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



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

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

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 - vbscript - 04/08/2015 

   n=15
   TextWindow.WriteLine("Recaman's sequence for the first " + n + " numbers:")
   recaman()
   TextWindow.WriteLine(Text.GetSubTextToEnd(recaman,2))
   n="firstdup"
   recaman()
   TextWindow.WriteLine("The first duplicate number in the Recaman's sequence is: " +firstdup)

Sub recaman 

   recaman=""
   firstdup=""
   If n="firstdup" Then
       n=1000
       firstdup="True"
   EndIf
   For i=0 To n-1
       p=ta[i-1]
       k=p+i
       If p<=i Then 
           ta[i]=k
           tb[k]=1
       Else
           m=p-i
           ta[i]=m
           If tb[m]=1 Then
               ta[i]=k
               tb[k]=1
           EndIf
       EndIf
       j=ta[i]
       If firstdup Then
           If dup[j]=1 Then
               firstdup=j
               Goto exitsub
           EndIf
           dup[j]=1
       EndIf
       recaman=recaman+","+j
   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 duplicate number in the Recaman's sequence is: 42

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

<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

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=283640"