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
```