Das Collatz-Problem ist eine unbewiesene Aussage über Folgen von natürlichen Zahlen.

Als erste Zahl der Folge wird eine natürliche Zahl gewählt. Die jeweils nächste Zahl der Folge ergibt sich aus der vorhergehenden Zahl

- durch Halbieren, wenn es eine gerade Zahl ist und ansonsten
- durch Verdreifachen und Addition von Eins.

Die Folge endet, wenn die Eins erreicht wird.

Unbewiesen ist, ob für jede beliebige erste natürliche Zahl immer nach endlich vielen Schritten die Eins erreicht wird.

Der folgende Ausdruck definiert eine rekursive Funktion, die als Eingabe die erste Zahl der Folge erwartet und die gesamte Folge als Liste zum Ergebnis hat.

(defproc collatz (n)
  (if
    (= n 1)
    (quote (1))
    (cons n
      (collatz
        (if
          (even? n)
          (/ n 2)
          (+ (* 3 n) 1))))))