Recaman's sequence: Difference between revisions
(Added Go) |
(→{{header|Go}}: Slight improvement.) |
||
Line 35: | Line 35: | ||
used[0] = true |
used[0] = true |
||
for n, foundDup := 1, false; n <= 15 || !foundDup || len(used) < 1001; n++ { |
for n, foundDup := 1, false; n <= 15 || !foundDup || len(used) < 1001; n++ { |
||
next := a[ |
next := a[n-1] - n |
||
if next < 1 || contains(a, next) { |
if next < 1 || contains(a, next) { |
||
next += 2 * n |
next += 2 * n |
Revision as of 15:15, 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.
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]
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)