Recaman's sequence: Difference between revisions

{{task}}

 

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

 

;Task:

# Generate and show here the first 15 members of the sequence.

# Find and show here, the first duplicated number in the sequence.

 

 

* [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.

<br><br>

 

{{trans|Python}}

 

‘The successor for a given Recaman term,

given the set of Recaman terms seen so far.’

print("First duplicated Recaman:\n "recamanUntil((seen, n, r, blnNew) -> !blnNew).last)

V setK = Set(enumFromTo(0)(1000))

 

{{out}}

 

=={{header|ALGOL W}}==

% calculate Recaman's sequence values %

 

reference(AValue) array hashTable ( 0 :: HMOD - 1 );

integer array A ( 0 :: 14 );

 

% adds an element to the hash table, returns true if an element with value An %

A( 0 ) := An1 := n := 0;

le1000Count := 0;

while le1000Count < 1000 do begin

logical le0, duplicate;

else if An <= 1000 then le1000Count := le1000Count + 1;;

if n < 15 then A( n ) := An;

An1 := An

end while_le1000Count_lt_1000 ;

);

% number of elements required to include the first 1000 integers %

end

 

{{out}}

<pre>

First duplicates: 20 24 (42)

first element to include all 1..1000: 328002

</pre>

 

=={{header|APL}}==

{{works with|Dyalog APL}}

genNext←{

R←⍵[N-1]-N←≢⍵

⎕←'Length of sequence containing [0..1000]:'

⎕←≢reca←genNext⍣{(⍳1001)∧.∊⊂⍺}⊢reca

 

{{out}}

The third of these tasks probably stretches Applescript a bit beyond the point of its usefulness – it takes about 1 minute to find the result, and even that requires the use of NSMutableSet, from the Apple Foundation classes.

 

use framework "Foundation"

use scripting additions

on unwords(xs)

intercalateS(space, xs)

{{Out}}

<pre>First 15 Recamans:

 

(Last result took c. 40 seconds to find)</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f RECAMANS_SEQUENCE.AWK

# converted from Microsoft Small Basic

exit(0)

}

{{out}}

<pre>

 

=={{header|BASIC}}==

20 PRINT "First 15 terms:"

30 FOR N=0 TO 14: GOSUB 100: PRINT A(N);: NEXT

140 NEXT

150 A(N)=X: RETURN

{{out}}

<pre>First 15 terms:

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

First repeated term:

A( 24 ) = 42</pre>

 

=={{header|C}}==

{{libheader|GLib}}

{{trans|Go}}

#include <stdlib.h>

#include <gmodule.h>

free(a);

return 0;

 

{{out}}

=={{header|C sharp|C#}}==

{{trans|Kotlin}}

using System.Collections.Generic;

 

}

}

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

=={{header|C++}}==

{{trans|C#}}

#include <ostream>

#include <set>

 

return 0;

{{out}}

<pre>The first 15 terms of the Recaman sequence are: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]

The first duplicated term is a[24] = 42

Terms up to a[328002] are needed to generate 0 to 1000</pre>

 

=={{header|D}}==

{{trans|Kotlin}}

 

void main() {

n++;

}

{{out}}

<pre>The first 15 terms of the Recaman sequence are: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]

The first duplicated term is a[24] = 42

Terms up to a[328002] are needed to generate 0 to 1000</pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>The first 15 terms are 0 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

 

=={{header|FOCAL}}==

01.20 F N=0,14;D 2;T %2,A(N)

01.30 T !"FIRST REPEATED"

02.50 I (Y)2.6,2.7,2.6

02.60 S A(N)=X;R

 

{{out}}

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Go}}==

 

 

import "fmt"

}

}

 

{{out}}

===Recursion===

A basic recursive function for the first N terms,

recaman n = fst <$> reverse (go n)

where

 

main :: IO ()

{{Out}}

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

Or, a little more flexibly, a '''recamanUpto''' (predicate) function.

{{Trans|JavaScript}}

import Data.Bool (bool)

 

, "Length of Recaman series required to include [0..1000]:"

, (show . length . recamanSuperset) $ fromList [0 .. 1000]

{{Out}}

<pre>First 15 Recamans:

For the third task, it would be enough to search through an infinite stream of Recaman-generated integer '''sets''' of increasing size, until we find the first that contains [0..1000] as a subset.

 

import Data.Maybe (fromJust)

import Data.Set (Set, fromList, insert, isSubsetOf, member)

"Length of Recaman series required to include [0..1000]:",

show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets

{{Out}}

<pre>First 15 Recamans:

</pre>

Let's write a binary search adverb.

average =: +/ % #

NB. extra_data u Bsearch bounds

NB. u is invoked as a dyad

Bsearch =: 1 :'((0 1 + (u <.@:average)) { ({. , <.@:average, {:)@:])^:_'

<pre>

NB. f expresses "not all [0, 1000] are in the first y members of list x"

=={{header|Java}}==

{{Trans|Kotlin}}

import java.util.HashSet;

import java.util.List;

}

}

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

=={{header|JavaScript}}==

{{Trans|Haskell}}

const main = () => {

 

// MAIN ------------------------------------------------

return main();

{{Out}}

<pre>First 15 Recaman:

all integers from [0..1000]:

328002</pre>

 

=={{header|Julia}}==

{{trans|Go}}

a = Vector{Int}([0])

used = Dict{Int, Bool}(0 => true)

 

recaman()

The first 15 terms of the Recaman sequence are [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]

The first duplicated term is a[25] = 42.

=={{header|Kotlin}}==

{{trans|Go}}

 

fun main(args: Array<String>) {

n++

}

 

{{output}}

This runs out of memory determining the final part :(

{{trans|C++}}

local used = {[0]=true}

local used1000 = {[0]=true}

end

n = n + 1

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

The first duplicated term is a[24] = 42

lua: not enough memory</pre>

 

=={{header|Microsoft Small Basic}}==

Inefficency of associative array allocation in Small Basic ban to provide the optional task.

nn=15

TextWindow.WriteLine("Recaman's sequence for the first " + nn + " numbers:")

EndFor

exitsub:

{{out}}

<pre>

 

=={{header|Nim}}==

 

iterator recaman(num: Positive = Natural.high): tuple[n, a: int; duplicate: bool] =

if target.card == 0:

echo "All numbers from 0 to 1000 generated after $1 terms.".format(n)

 

{{out}}

=={{header|Objeck}}==

{{trans|Java}}

 

class RecamanSequence {

return out;

}

 

{{output}}

 

=={{header|Perl}}==

 

$max = 1000;

print "First fifteen terms of Recaman's sequence: " . join(' ', @recamans[0..14]) . "\n";

print "First duplicate at term: a[$dup]\n";

{{out}}

<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

=={{header|Phix}}==

{{trans|D}}

{{out}}

<pre>

=={{header|PHP}}==

{{trans|Java}}

$a = array();

array_push($a, 0);

$n++;

}

 

{{out}}

Terms up to a[328002] are needed to generate 0 to 1000

</pre>

 

=={{header|PureBasic}}==

Dim a.i(#MAX)

Dim b.b(1)

PrintN("Number of Recaman terms needed to generate all integers from [0..1000]: "+Str(fit1000))

Input()

{{out}}

<pre>First 15 terms: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

=={{header|Python}}==

===Conditional iteration over a generator===

 

class Recamans():

if setn.issubset(recamans.a):

print(f"Range 0 ..{n} is covered by terms up to a({recamans.n})")

 

{{out}}

 

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

 

 

 

if __name__ == '__main__':

{{Out}}

<pre>First 15 Recaman:

( This version is still c. 8X faster than the ''conditional iteration over generator'' version, as measured by a simple start and end test using ''time.time()'' ).

 

 

from itertools import (islice)

# MAIN ---

if __name__ == '__main__':

<pre>First 15 Recaman:

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

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

328002</pre>

 

=={{header|R}}==

A bit slow because the append() function is expensive.

visited <- vector('logical', 1e8)

 

}

}

{{out}}

<pre>

{{works with|Rakudo|2018.06}}

 

state %seen;

state $term;

@seen[$this] = 1;

say "Range 0..1000 covered by terms up to a[{$i - 1}]" and last if ++$ == 1001;

{{out}}

<pre>First fifteen terms of Recaman's sequence: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

could've been replaced with:

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

parse arg N h . /*obtain optional arguments from the CL*/

if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/

end

$= $ z /*add number to $ list?*/

{{out|output|text=&nbsp; when using the default input:}}

 

 

===version 2===

/*improved using version 1's method for task 3 */

Call time 'R' /* Start timer */

Have.temp=1

End

{{out}}

<pre>the first 15 elements: 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9

 

=={{header|Ring}}==

load "zerolib.ring"

 

see "" + dupnr + "] = " + duplicate + nl

see "done..." + nl

{{out}}

<pre>

the first duplicated term is a[24] = 42

done...

</pre>

 

=={{header|Ruby}}==

{{trans|Kotlin}}

 

a = [0]

end

n = n + 1

{{out}}

<pre>The first 15 terms of the Recaman's sequence are [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9]

The first duplicated term is a[24] = 42

Terms up to a[328002] are needed to generate 0 to 1000</pre>

 

=={{header|Scala}}==

{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/xjLHy7m/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/FdJaIB68S8i5OSndpigBtA Scastie (remote JVM)].

 

object RecamansSequence extends App {

println(s"The first 15 terms of the Recaman sequence are : ${a.take(15)}")

 

 

=={{header|Sidef}}==

 

var term = 0

}

}

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

 

=={{header|uBasic/4tH}}==

Print "First 15 numbers:"

 

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)

Proc _Set(Set(a, b)) ' set bit in bitmap

Next

_Poke Param(2) : Return (Or(@(a@), Shl(1, b@)))

_Peek Param(1) : Return (And(@(a@/32), Shl(1, a@%32))>0)

{{out}}

<pre>

{{trans|Rexx}}

To run in console mode with cscript.

nx=15

h=1000

next 'n

recaman=list

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Imports System.Collections.Generic

 

Next

End Sub

<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

=={{header|Wren}}==

{{trans|Kotlin}}

var used = { 0: true }

var used1000 = { 0: true }

}

n = n + 1

 

{{out}}

 

=={{header|zkl}}==

Walker.tweak(fcn(rn,rp,d){

n,p,a := rn.value, rp.value, p - n;

return(rn.inc(),a,d[a]>1);

}.fp(Ref(0),Ref(0),Dictionary()) )

recamanW().walk(15).apply("get",1).println();

 

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

{{out}}

<pre>