Van Eck sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(Promote to full task status.)
(→‎{{header|REXX}}: optimized the code, it's over three times faster now.)
Line 254: Line 254:
if s.2=='' | s.2=="," then s.2= 991 /* " " " " " " */
if s.2=='' | s.2=="," then s.2= 991 /* " " " " " " */
if e.2=='' | e.2=="," then e.2= 1000 /* " " " " " " */
if e.2=='' | e.2=="," then e.2= 1000 /* " " " " " " */
mx= max(e.1, e.2) /*MX: is the largest (range) "end". */
mx= max(e.1, e.2) /*MX: is the largest (range) "end". */
$= 0 /*the initial (start) value of the seq.*/
$= 0; z= $; @= /*initial value of sequence; Z= last.*/
do j=1 for mx; $= $ wordpos( reverse( word($, j)), reverse( subword($, 1, j-1)) )
do j=1 for mx; z= wordpos( reverse(z), reverse($$) ); $$=$; $= $ z
end /*j*/ /*@: is the $ string less last value.*/
end /*j*/


do r=1 for 2; L= length(mx) /*L: is the width of the largest "end"*/
do r=1 for 2; L= length(mx) /*L: is the width of the largest "end"*/

Revision as of 20:54, 18 June 2019

Task
Van Eck sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The sequence is generated by following this pseudo-code: 

A:  The first term is zero.
    Repeatedly apply:
        If the last term is *new* to the sequence so far then:
B:          The next term is zero.
        Otherwise:
C:          The next term is how far back this last term occured previousely.


Example

Using A:

0

Using B:

0 0

Using C:

0 0 1

Using B:

0 0 1 0

Using C: (zero last occured two steps back - before the one)

0 0 1 0 2

Using B:

0 0 1 0 2 0

Using C: (two last occured two steps back - before the zero)

0 0 1 0 2 0 2 2

Using C: (two last occured one step back)

0 0 1 0 2 0 2 2 1

Using C: (one last appeared six steps back)

0 0 1 0 2 0 2 2 1 6

...

Task
  1. Create a function/proceedure/method/subroutine/... to generate the Van Eck sequence of numbers.
  2. Use it to display here, on this page:
  1. The first ten terms of the sequence.
  2. Terms 991 - to - 1000 of the sequence.
References


Clojure

<lang clojure>(defn van-eck 

 ([] (van-eck 0 0 {}))
 ([val n seen]
  (lazy-seq
   (cons val
         (let [next (- n (get seen val n))]
           (van-eck next
                    (inc n)
                    (assoc seen val n)))))))

(println "First 10 terms:" (take 10 (van-eck))) (println "Terms 991 to 1000 terms:" (take 10 (drop 990 (van-eck))))</lang>

Output:
First 10 terms: (0 0 1 0 2 0 2 2 1 6)
Terms 991 to 1000 terms: (4 7 30 25 67 225 488 0 10 136)

Go

<lang go>package main

import "fmt"

func main() { 

   const max = 1000
   a := make([]int, max) // all zero by default
   for n := 0; n < max-1; n++ {
       for m := n - 1;  m >= 0; m-- {
           if a[m] == a[n] {
               a[n+1] = n - m
               break
           }    
       }
   }
   fmt.Println("The first ten terms of the Van Eck sequence are:")
   fmt.Println(a[:10])
   fmt.Println("\nTerms 991 to 1000 of the sequence are:")
   fmt.Println(a[990:])

}</lang>

Output:
The first ten terms of the Van Eck sequence are:
[0 0 1 0 2 0 2 2 1 6]

Terms 991 to 1000 of the sequence are:
[4 7 30 25 67 225 488 0 10 136]

Alternatively, using a map to store the latest index of terms previously seen (output as before): <lang go>package main

import "fmt"

func main() { 

   const max = 1000
   a := make([]int, max) // all zero by default
   seen := make(map[int]int)
   for n := 0; n < max-1; n++ {
       if m, ok := seen[a[n]]; ok {
           a[n+1] = n - m            
       } 
       seen[a[n]] = n          
   }
   fmt.Println("The first ten terms of the Van Eck sequence are:")
   fmt.Println(a[:10])
   fmt.Println("\nTerms 991 to 1000 of the sequence are:")
   fmt.Println(a[990:])

}</lang>

Perl 6

There is not a Van Eck sequence, rather a series of related sequences that differ in their starting value. This task is nominally for the sequence starting with the value 0. This Perl 6 implementation will handle any integer starting value.

Specifically handles:

among others.

Implemented as lazy, extendable lists.

<lang perl6>sub n-van-ecks ($init) { 

   $init, -> $i, {
       state %v;
       state $k;
       $k++;
       my $t  = %v{$i}.defined ?? $k - %v{$i} !! 0;
       %v{$i} = $k;
       $t
   } ... *

}

for < 

   A181391 0
   A171911 1
   A171912 2
   A171913 3
   A171914 4
   A171915 5
   A171916 6
   A171917 7
   A171918 8

> -> $seq, $start { 

   my @seq = n-van-ecks($start);

   # The task
   put qq:to/END/

   Van Eck sequence OEIS:$seq; with the first term: $start
           First 10 terms: {@seq[^10]}
   Terms 991 through 1000: {@seq[990...999]}
   END

}</lang>

Output:
Van Eck sequence OEIS:A181391; with the first term: 0
        First 10 terms: 0 0 1 0 2 0 2 2 1 6
Terms 991 through 1000: 4 7 30 25 67 225 488 0 10 136


Van Eck sequence OEIS:A171911; with the first term: 1
        First 10 terms: 1 0 0 1 3 0 3 2 0 3
Terms 991 through 1000: 0 6 53 114 302 0 5 9 22 71


Van Eck sequence OEIS:A171912; with the first term: 2
        First 10 terms: 2 0 0 1 0 2 5 0 3 0
Terms 991 through 1000: 8 92 186 0 5 19 41 413 0 5


Van Eck sequence OEIS:A171913; with the first term: 3
        First 10 terms: 3 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 5 5 1 17 192 0 6 34 38 179


Van Eck sequence OEIS:A171914; with the first term: 4
        First 10 terms: 4 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 33 410 0 6 149 0 3 267 0 3


Van Eck sequence OEIS:A171915; with the first term: 5
        First 10 terms: 5 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 60 459 0 7 13 243 0 4 10 211


Van Eck sequence OEIS:A171916; with the first term: 6
        First 10 terms: 6 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 6 19 11 59 292 0 6 6 1 12


Van Eck sequence OEIS:A171917; with the first term: 7
        First 10 terms: 7 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 11 7 2 7 2 2 1 34 24 238


Van Eck sequence OEIS:A171918; with the first term: 8
        First 10 terms: 8 0 0 1 0 2 0 2 2 1
Terms 991 through 1000: 16 183 0 6 21 10 249 0 5 48

Python

<lang python>def van_eck(): 

   n, seen, val = 0, {}, 0
   while True:
       yield val
       last = {val: n}
       val = n - seen.get(val, n)
       seen.update(last)
       n += 1
  1. %%

if __name__ == '__main__': 

   print("Van Eck: first 10 terms:  ", list(islice(van_eck(), 10)))
   print("Van Eck: terms 991 - 1000:", list(islice(van_eck(), 1000))[-10:])</lang>
Output:
Van Eck: first 10 terms:   [0, 0, 1, 0, 2, 0, 2, 2, 1, 6]
Van Eck: terms 991 - 1000: [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]

Python: Alternate

The following stores the sequence so far in a list seen rather than the first example that just stores last occurrences in a dict. <lang python>def van_eck(): 

   n = 0
   seen = [0]
   val = 0
   while True:
       yield val
       if val in seen[1:]:
           val = seen.index(val, 1)
       else:
           val = 0
       seen.insert(0, val)
       n += 1</lang>
Output:

As before.

REXX

This REXX version allows the   start   and   end   of two Van Eck sequences   (to be displayed). <lang rexx>/*REXX program generates/displays two 'start' to 'end' elements of the Van Eck sequence.*/ parse arg s.1 e.1 s.2 e.2 . /*obtain optional arguments from the CL*/ if s.1== | s.1=="," then s.1= 1 /*Not specified? Then use the default.*/ if e.1== | e.1=="," then e.1= 10 /* " " " " " " */ if s.2== | s.2=="," then s.2= 991 /* " " " " " " */ if e.2== | e.2=="," then e.2= 1000 /* " " " " " " */ 

                mx= max(e.1, e.2)               /*MX:  is the largest (range)  "end".  */

$= 0; z= $; @= /*initial value of sequence; Z= last.*/ 

    do j=1  for mx;  z= wordpos( reverse(z),  reverse($$) );      $$=$;        $= $ z
    end   /*j*/                                 /*@:   is the $ string less last value.*/

    do r=1  for 2;         L= length(mx)        /*L:  is the width of the largest "end"*/
    say 'terms'  right(s.r,L)  " through "  right(e.r,L)': '   subword($, s.r, e.r-s.r+1)
    end   /*r*/                                 /*stick a fork in it,  we're all done. */</lang>
output   when using the default inputs:
terms    1  through    10:  0 0 1 0 2 0 2 2 1 6
terms  991  through  1000:  4 7 30 25 67 225 488 0 10 136

Scala

<lang scala> object VanEck extends App { 

 def vanEck(n: Int): List[Int] = {

   def vanEck(values: List[Int]): List[Int] =
     if (values.size < n)
       vanEck(math.max(0, values.indexOf(values.head, 1)) :: values)
     else
       values

   vanEck(List(0)).reverse
 }

 val vanEck1000 = vanEck(1000)
 println(s"The first 10 terms are ${vanEck1000.take(10)}.")
 println(s"Terms 991 to 1000 are ${vanEck1000.drop(990)}.")

} </lang>

Output:
The first 10 terms are List(0, 0, 1, 0, 2, 0, 2, 2, 1, 6).
Terms 991 to 1000 are List(4, 7, 30, 25, 67, 225, 488, 0, 10, 136).
Retrieved from "https://rosettacode.org/wiki/Van_Eck_sequence?oldid=291189"