Recaman's sequence: Difference between revisions
(Added C) |
(Added Kotlin) |
||
Line 159: | Line 159: | ||
{{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> |
||
=={{header|Kotlin}}== |
|||
{{trans|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}} |
|||
<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|Python}}== |
=={{header|Python}}== |
Revision as of 15:59, 4 August 2018
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
- 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.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- define TRUE 1
- 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
<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
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)