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.
Programming Praxis 
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)
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!
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))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)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: