Distribution of Collatz Lengths
Desription of the problem
Consider the following function \[ f(n) = \begin{cases} \frac{n}{2} & \text{ if $n$ is even }\\ 3n + 1 & \text{ otherwise } \end{cases} \] and the recursive sequence \(a_{n+1} = f(a_n)\). It was conjectured that the sequence will produce \(1\) eventually for every initial value \(a_0\). Despite the very simple description, this turns out to be a notoriously difficult problem to solve.
Today, I will write a short lisp program to perform some numerical experiments on the problem. Also, I noticed that there there were no visualizations of the distribution of the lengths of the recursive sequences I defined above for different initial values.
Lisp code
I will start with the function:
(defun f(n)
(if (evenp n)
(/ n 2)
(1+ (* 3 n))))
Fand then another function which will iterate `f` until it hits 1
(defvar upper-limit (expt 2 22))
(defparameter iterate-table (make-hash-table :test 'equal))
(defun iterate-lookup (x) (gethash x iterate-table))
(defun iterate-push (x val) (setf (gethash x iterate-table) val))
(defun iterate(n)
(if (= n 1)
0
(or (iterate-lookup n)
(let ((temp (1+ (iterate (f n)))))
(if (< n upper-limit)
(iterate-push n temp)
temp)))))
ITERATELet me run the code:
(time (loop for n from 1 to upper-limit
do (iterate n)))
Evaluation took:
4.724 seconds of real time
4.716294 seconds of total run time (4.628289 user, 0.088005 system)
[ Run times consist of 0.072 seconds GC time, and 4.645 seconds non-GC time. ]
99.83% CPU
11,310,793,128 processor cycles
171,957,200 bytes consed
(with-open-file (results "collatz.csv"
:direction :output
:if-exists :supersede
:if-does-not-exist :create)
(maphash (lambda (x y) (format results "~A ~A~%" x y)) iterate-table))
NILAnd here is the distribution of the lengths of the Collatz sequences for all initial values between 1 and \(2^{22}\)
