Van Eck Sequence

June 14, 2019

We maintain an a-list prev that stores, for each v in the list, the index i at which it appears. There will be one entry in the a-list for each member of the sequence; repeated sequence entries will appear multiple times, and assoc will return the most recent, which stores the associated index:

(define-generator (van-eck)
  (let loop ((v 0) (i 0) (prev (list)))
    (yield v)
    (let ((t v))
      (let ((v (- i (cond ((assoc v prev) => cdr) (else i)))))
        (loop v (+ i 1) (cons (cons t i) prev))))))

Here is the function in action:

> (take-gen 25 (van-eck))
(0 0 1 0 2 0 2 2 1 6 0 5 0 2 6 5 4 0 5 3 0 3 2 9 0)

You can run the program at https://ideone.com/tKuo7T.

Advertisements

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: