Van Eck sequence

Van Eck sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

• Don't Know (the Van Eck Sequence) - Numberphile video.
• Wikipedia Article: Van Eck's Sequence.
• OEIS sequence: A181391.

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

Implemented as a lazy, extendable list.

<lang perl6>sub next-van-eck ( $i, $k ) {

   state %v;
   my $t  = %v{$i}.defined ?? $k - %v{$i} !! 0;
   %v{$i} = $k;
   $t

}

my @Van-Ecks = 0, *.&next-van-eck($++) ... *;

1. The task

put "Van-Eck sequence:

       First 10 terms: {@Van-Ecks[^10]}

Terms 991 through 1000: {@Van-Ecks[990...999]}";

1. And just for the heck of it.

for 1e3, 1e4, 1e5 {

   my ($k, $v) = @Van-Ecks.first: * > $_, :kv;
   printf "%22s: %d at position %d\n", "First term > $_", $v, $k+1;

}</lang>

Output:

Van-Eck sequence:
        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
     First term > 1000: 1024 at position 1150
    First term > 10000: 10381 at position 11603
   First term > 100000: 100881 at position 104511

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 s1 e1 s2 e2 . /*obtain optional arguments from the CL*/ if s1== | s1=="," then s1= 1 /*Not specified? Then use the default.*/ if e1== | e1=="," then e1= 10 /* " " " " " " */ if s2== | s2=="," then s2= 991 /* " " " " " " */ if e2== | e2=="," then e2= 1000 /* " " " " " " */

               mx= max(e1, e2);  L= length(mx)  /*MX: largest end;    L: width of  MX. */

$=0 /*the initial (start) value of the seq.*/

   do j=1  for mx;   #= words($)
   if wordpos(z,$)==#  then $= $ 0
                       else $= $ wordpos(reverse(word($,#)), reverse(subword($, 1, #-1)))
   end   /*j*/
                                                /*stick a fork in it,  we're all done. */

say 'terms' right(s1, L) " through " right(e1, L)': ' subword($, s1, e1-s1+1) say 'terms' right(s2, L) " through " right(e2, L)': ' subword($, s2, e2-s2+1)</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