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.

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