Van Eck’s Sequence

Description of the problem:

Next in the line of interesting sequences from The On-Line Encyclopedia of Integer Sequences is Van Eck’s sequence. Here is how it is defined:

Given the initial part of the sequence \(a_1,\ldots,a_n\) if \(a_n\) appears for the first time in the sequence, we set \(a_{n+1}\) to 0. Otherwise, we set \(a_{n+1}\) to \(n-m\) where \(a_m\) is the first time \(a_n\) appears in the sequence.

An implementation in common lisp

It is easier to grow lists in common lisp at the head. So, we are going to construct Van Eck’s sequence in the reverse:

(defun van-eck (xs)
  (cond
    ((null xs) (list 0))
    ((not (member (car xs) (cdr xs))) (cons 0 xs))
    (t (cons (1+ (position (car xs) (cdr xs))) xs))))

VAN-ECK

Next, we write the iterator

(defun iterate (fn init n &optional xs)
  (do ((i 0 (1+ i))
       (r (funcall fn init) (funcall fn r)))
      ((= i n) (nreverse r))))

ITERATE

Let us test:

(iterate #'van-eck nil 50)

(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 4 9 3 6 14 0 6 3 5 15 0 5 3
 5 2 17 0 6 11 0 3 8 0 3 3 1)