The Kitchen Sink and Other Oddities

Atabey Kaygun

Collatz Lengths (Continued)

I was looking at the following function f:NN defined as f(n)={1 if n=1n2 if n is even3n+12 otherwise and the recursive function (n)={0 if n=11+(f(n)) otherwise  I am specifically interested in (n)/log2(n).

Yesterday, I made a mistake in typing in f(n) and instead I defined g(n)={1 if n=1,3n2 if n is even3(n+1)2 otherwise and I didn’t notice the mistake until later. If you have experimented with Collatz lengths you should know that it is a rather interesting accident that the recursive length terminates. So, having found another function whose termination behavior is similar to the original f(n) is nice.

This gave me an idea: what if I plotted the lengths of sequences coming from f(n) and g(n) against each other would I see that the convergence behaviors of the recursive lengths are similar.

Code

First I will need our functions:

(defun f (n)
   (cond ((= n 1) 1)
         ((evenp n) (/ n 2))
         (t (/ (1+ (* 3 n)) 2))))
F


(defun g (n)
   (cond ((< n 4) 1)
         ((evenp n) (/ n 2))
         (t (* (/ 3 2) (1+ n)))))
G

Then an iterator:

(defun iterate (fn n &optional (m 0))
   (if (= n 1)
      m
      (iterate fn (funcall fn n) (1+ m))))
ITERATE

Next, the data on lengths:

(let ((n (expt 2 22))
      (filename "collatz7Data.csv"))
   (with-open-file (out filename
                        :direction :output
                        :if-exists :supersede
                        :if-does-not-exist :create)
      (loop for i from 2 to n
            do (let ((x (log i 2)))
                   (format out "~d ~4,1f ~4,1f~%"
                               i
                               (/ (iterate #'f i) x)
                               (/ (iterate #'g i) x))))))
NIL