Linus Sequence

Description of the problem:

Given a finite sequence \((a_n)\) of letters 1 and 2, let us call the repeated tail as the longest contiguous subsequence \((b_n)\) of \((a_n)\) with the property that one can write \((a_n)\) as \[ (a_n) = (c_n) (b_n) (b_n) \] The product on the right hand side is the concatenation.

Now, a linus sequence is a recursively defined sequence of 1’s and 2’s. Given \(a_1,\ldots,a_k\), we choose \(a_{k+1}\) in such a way that the repeated tail of the new augmented sequence \(a_1,\ldots,a_{k+1}\) is the shortest among all possible choices.

This is the sequence A006345 in The Encyclopedia of Integer Sequences.

An implementation in Common Lisp

First, I need a function that checks if given a sequence forms the beginning segment of another sequence:

(defun starts-with-p (bs as)
  (cond ((null bs) t)
        ((null as) nil)
        ((equal (car bs) (car as)) (starts-with-p (cdr bs) (cdr as)))
        (t nil)))

STARTS-WITH-P

Next, a function that calculates the length of the longest repeated initial segment. My implementation constructs the sequence in the reverse, by adding new terms at the beginning:

(defun check-linus (as &optional bs (r 0))
  (if (null as)
      r
      (check-linus (cdr as)
                   (append bs (list (car as)))
                   (if (starts-with-p bs as)
                       (length bs)
                       r))))

CHECK-LINUS

Finally, an iterator function:

(defun linus-iterate (xs)
  (let ((as (cons 1 xs))
        (bs (cons 2 xs)))
    (if (< (check-linus bs) (check-linus as))
        bs
        as)))

LINUS-ITERATE

Let us get the first 100 terms. Since I got augmented sequences by adding new terms at the beginning, the code returns the reverse of the constructed sequence:

(do ((i 1 (1+ i))
     (r nil (linus-iterate r)))
    ((= i 100) (reverse r)))

(1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 1 1 2 2 1 2 1 1 2 2 1 1 1 2 1 1 2 2 1 2 1
 1 2 1 2 2 1 1 2 1 1 1 2 2 1 2 1 1 2 2 1 2 2 2 1 1 2 1 2 2 1 1 2 2 2 1 2 2 1 1
 2 1 2 2 1 2 1 1 2 2 1 2 2 2 1 1 2 1 2 2 1)