[Common Lisp] Q数を SERISE で

『ゲーデル、エッシャー、バッハ―あるいは不思議の環』に出てきた Q数 というのを SERIES で生成してみた。Q数というのは

n>2のときQ(n)=Q(n-Q(n-1))+Q(n-Q(n-2)),Q(1)=Q(2)=1

で、規則的に生成しているけど順番に増加せず増えたり減ったりしながら増加している。「非常に規則的なしかだで作り出される混沌」と表現されている。

次のコードは最初の1000個を出力する。

(require :series)
(use-package :series)
(subseries
 (scan-fn '(values integer integer list)
          (lambda () (values 1 2 '(1 1)))
          (lambda (a n list)
            (declare (ignore a))
            (let ((x (+ (nth (- n (nth (- n 1) list)) list)
                        (nth (- n (nth (- n 2) list)) list))))
              (values x
                      (1+ n)
                      (append list (list x))))))
 0 1000)

おもしろい。