Collatz sequence (yet again)

Description of the problem:

I will consider the following function 

\[ f(1) = 1, \quad f(n) = f(n/2) \text{ if $n$ is even },\quad f(n) = 3n+1  \text{ otherwise } \] 

and the recursive sequence \[ a_{n+1} = f(a_n) \] with an arbitrary initial value \(a_0\).

Famous Collatz conjecture states that this sequence always stabilizes with tail being an infinite sequence of 1’s.

Today, I am interested in the expected value of the 2-part of the sequence until it terminates at 1. In particular, I would like to calculate \[ E(a_0) = \frac{1}{\ell(a_0)} \sum_n \nu_2(a_n) \] where \[ \nu_2(n) = \max\{m\in\mathbb{N}\mid 2^m \text{ divides } n\} \] and \(\ell(a_0)\) is the length of the Collatz sequence starting at \(a_0\).

Implementation

Let us write our functions

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

(defun nu2(n &optional (acc 0))
   (if (oddp n)
       acc
       (nu2 (/ n 2) (1+ acc))))

(defun collatz (a0 &optional acc)
   (if (= a0 1)
       (nreverse acc)
       (collatz (f a0) (cons a0 acc))))

(defun expected (a0)
   (let ((xs (collatz a0)))
      (/ (reduce #'+ (mapcar #'nu2 xs))
         (length xs)
         1.0)))

F
NU2
COLLATZ
EXPECTED

Let us see the plot of the expected values between 2 and 50000:

(with-open-file (out "collatz-2part-data.csv"
                     :direction :output
                     :if-exists :supersede
                     :if-does-not-exist :create)
   (loop for i from 2 to 50000 do
       (format out "~4d, ~4,3f~%" i (expected i))))

NIL