Recaman's sequence: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Cut down on unnecessary calculations, reduce run time significantly) |
Walterpachl (talk | contribs) (added REXX verion 2) |
||
Line 475: | Line 475: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
|||
<lang rexx>/*REXX program computes & displays the Recaman sequence (also known as Recamán sequence)*/ |
<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*/ |
parse arg N h . /*obtain optional arguments from the CL*/ |
||
Line 507: | Line 508: | ||
The first duplicate number in the Recamán's sequence is: 42 |
The first duplicate number in the Recamán's sequence is: 42 |
||
</pre> |
</pre> |
||
===version 2=== |
|||
<lang rexx>/*REXX program computes & displays the Recaman sequence */ |
|||
oid='recpe.txt'; 'erase' oid |
|||
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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
Revision as of 18:46, 5 August 2018
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
- 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
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. <lang haskell>import Data.Set (Set, fromList, insert, isSubsetOf, member, size)
recamanUpto :: (([Int], Int, Set Int) -> Bool) -> ([Int], Int, Set Int) recamanUpto p =
until p (\(rs@(r:_), i, set) -> let nxt = nextRecaman set i r in (nxt : rs, succ i, insert nxt set)) ([0], 1, fromList [0])
nextRecaman :: Set Int -> Int -> Int -> Int nextRecaman set i nRec =
let back = nRec - i in if 0 < back && not (member back set) then back else nRec + i
firstNRecamans :: Int -> [Int] firstNRecamans n =
let (rs, _, _) = recamanUpto (\(_, i, _) -> n == i) in reverse rs
firstDuplicateR :: Int firstDuplicateR =
let (rs, _, _) = recamanUpto (\(rs, _, set) -> size set /= length rs) in head rs
recamanSuperSet :: Set Int -> [Int] recamanSuperSet setInts =
let (rs, _, _) = recamanUpto (\(_, _, setR) -> isSubsetOf setInts setR) in tail rs
-- TEST --------------------------------------------------------------- main :: IO () main =
putStrLn $ unlines [ "First 15 Recamans:" , show $ firstNRecamans 15 , "\nFirst duplicated Recaman:" , show firstDuplicateR , "\nLength 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
<lang javascript>(() => {
const main = () => {
console.log( 'First 15 Recaman:\n' + recamanUpto(i => i === 15) );
console.log( '\n\nFirst duplicated Recaman:\n' + last(recamanUpto( (_, set, rs) => set.size !== rs.length )) );
const setK = new Set(enumFromToInt(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 --------------------------------------------
// nextRecaman :: Set Int -> Int -> Int const nextRecaman = (setSeen, i, nRec) => { const back = nRec - i; return (0 < back && !setSeen.has(back)) ? ( back ) : nRec + i; };
// recamanUpto :: (Int -> Set Int > [Int] -> Bool) -> [Int] const recamanUpto = p => { let i = 1, intR = 0, rs = [intR]; const setR = new Set(rs); while (!p(i, setR, rs)) { intR = nextRecaman(setR, i, intR); setR.add(intR); rs.push(intR); i++; } return rs; }
// GENERIC --------------------------------------------
// enumFromToInt :: Int -> Int -> [Int] const enumFromToInt = (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
<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+"]="+firstdup)
Sub recaman
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 EndIf EndIf If firstdup Then If dup[a[n]]=1 Then firstdup=a[n] 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
<lang perl6>my @recamans = 0, {
state %s; state $n; $n++; my $k = $^m - $n; $k = $m + $n unless ($k > 0) && !%s{$k}; %s{$k} = True; $k
} … *;
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 = 0 xx 1001; for ^Inf {
next if (my $this = @recamans[$_]) > 1000 or @seen[$this]; @seen[$this] = 1; say "Range 0..1000 covered by terms up to a[$_]" and last if sum(@seen[^1001]) == 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 */ oid='recpe.txt'; 'erase' oid 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)