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.
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-PNext, 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-LINUSFinally, 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-ITERATELet 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)