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