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

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:

• OIES:A181391 - Van Eck sequence starting with 0
• OIES:A171911 - Van Eck sequence starting with 1
• OIES:A171912 - Van Eck sequence starting with 2
• OIES:A171913 - Van Eck sequence starting with 3
• OIES:A171914 - Van Eck sequence starting with 4
• OIES:A171915 - Van Eck sequence starting with 5
• OIES:A171916 - Van Eck sequence starting with 6
• OIES:A171917 - Van Eck sequence starting with 7
• OIES:A171918 - Van Eck sequence starting with 8

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 /*the initial (start) value of the seq.*/

    do j=1  for mx;  $= $ wordpos( reverse( word($, j)),  reverse( subword($, 1, j-1))  )
    end   /*j*/

    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).