Van Eck Sequence

June 14, 2019

Neil Sloane is on Numberphile again, discussing the Van Eck sequence (A181391):

The first item in the sequence is 0. Compute the next item as follows: If the previous item has not previously appeared in the sequence, add 0 to the sequence, otherwise add to the sequence the number of steps back in the sequence the previous item previously appeared. For instance, the first item is 0. Since 0 has not previously appeared in the sequence, the next item is 0. Now 0 has previously appeared, and the previous 0 was one back in the sequence, so add 1 to the sequence. Since 1 has not previously appeared, add 0. But 0 appeared previously, two back in the sequence, so add 2. Since 2 has not previously appeared, add 0. But 0 appeared previously, two items back, so add 2 to the sequence. Since 2 previously appeared in the sequence, two terms back, add another 2 to the sequence. The next item in the sequence is 1, because 2 also appeared as the previous number. Since 1 appeared in the sequence, count back to the previous 1, and add 6 to the sequence. And so on. The sequence begins 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, ….

Your task is to write a program that generates the Van Eck sequence and investigate the properties of the sequence. When you are finished, you are welcome to ,a href=”https://programmingpraxis.com/2019/06/14/van-eck-sequence/2/”>read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

4 Responses to “Van Eck Sequence”

  1. Zack said

    Fun little sequence, though not much of a programming challenge. Here is my take on it using Julia 1.0:

    function main(n::Int64 = 100)
    x = zeros(Int64, n)

    for i = 3:n
        z = x[i-1]
    
        for j = (i-2):-1:1
    
            if x[j] == z
                x[i] = i - j - 1
                break
            end
        end
    end
    
    return x
    

    end

    Interestingly, the sequence yields larger gaps towards the higher numbers, for the samples tested. This makes the sequence “complete” for the early part of it, a pattern that is likely to continue for larger samples. Still not convinced about its usefulness, but a fun little exercise nevertheless. Have a nice weekend!

  2. Paul said

    In Python.

    def vaneck():
        L, x, n, prev = {}, 0, 0, -1
        while True:
            yield x
            L[prev], prev, n = n, x, n+1
            x = max(0, n - L.get(prev, n))
    
  3. chaw said

    Here is a R7RS Scheme + (srfi 69) solution that runs in linear time
    (or constant time per element if implemented as a generator), with the
    usual hash-table caveat.

    (import (scheme base)
            (scheme write)
            (only (srfi 69)
                  make-hash-table hash-table-ref/default hash-table-set!
                  hash-table-size))
    
    (define (display-van-eck-sequence num-elements unique-count-only?)
      ;; ht[x] = max 0-based index i s.t. seq(i) = x, where seq is
      ;; sequence of elements already outputted, except the very last
      ;; (previous) one. ht[-1] = -1 is a special base case.
      (let ((ht (make-hash-table =)))
        ;; loop on current index and previous item:
        (let loop ((idx 0)
                   (prev-item -1))
          (when (< idx num-elements)
            (let ((item (- idx
                           (hash-table-ref/default ht
                                                   prev-item
                                                   idx))))
              (unless unique-count-only? (display item))
              (hash-table-set! ht prev-item idx)
              (loop (+ idx 1)
                    item))))
        (newline)
        (display (hash-table-size ht))
        (newline)))
    
    (display-van-eck-sequence 20 #f)
    (display-van-eck-sequence 1000 #t)
    (display-van-eck-sequence #e1e6 #t)
    

    0 0 1 0 2 0 2 2 1 6 0 5 0 2 6 5 4 0 5 3
    7
    
    198
    
    136529
    

  4. Daniel said

    Here’s a solution in C++.

    #include <cstdlib>
    #include <iostream>
    #include <unordered_map>
    
    using namespace std;
    
    int main(int argc, char* argv[]) {
      if (argc != 2) return EXIT_FAILURE;
      int n = stoi(argv[1]);
      int current = 0;
      int next = 0;
      unordered_map<int, int> map;
      for (int i = 0; i < n; ++i) {
        current = next;
        if (map.count(current)) {
          next = i - map[current];
        } else {
          next = 0;
        }
        cout << current << endl;
        map[current] = i;
      }
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./a.out 18
    0
    0
    1
    0
    2
    0
    2
    2
    1
    6
    0
    5
    0
    2
    6
    5
    4
    0
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: