Collatz Sequences (Continued)

Description of the problem

I am going to continue my (naive) investigation into Collatz Conjecture. In sort, the conjecture says that repeated applications of the following function \[ f(n) = \begin{cases} 1 & \text{ if $n=1$ }\\ 3n+1 & \text{ if $n\neq 1$ is odd }\\ f(n/2) & \text{ if $n$ is even } \end{cases} \] will allways stabilize at 1.

Some number theory and non-archimedian norms

A non-archimedian norm is a function which associates a length $\|\|x\|\|$ for elements $x\in X$ in an ablian group (assume $X$ has addition) which satisfies \[ \|\|x+y\|\|\leq \max(\|\|x\|\|,\|\|y\|\|) \] as opposed to the classical triangle inequality.

Fix a prime number $p$, then given a number $n\in\mathbb{Z}$ define $\nu_p(n)$ as the greatest natural number $c$ such that $p^c$ divides $n$. Then $\|\|n\|\|_p = 2^{-\nu(n)}$ is a non-archimedian norm on the ring of integers. In this post, I will use $p=2$ and drop the subscript on the norm notation.

Let me split our function $f(n)$ we defined above into composition of two functions: \[ a(n) = \begin{cases} 1 & \text{ if } n=1\\ 3n+1 & \text{ otherwise } \end{cases} \quad\text{ and }\quad b(n) = \begin{cases} b(n/2) & \text{ if $n$ is even }\\ n & \text{ otherwise } \end{cases} \] Then \[ f(n) = \begin{cases} a(n) & \text{ if $n$ is odd }\\ ab(n) & \text{ if $n$ is even} \end{cases} = ab(n) \]

Notice that the function $b$ projects an element $x\in\mathbb{Z}$ into the set of elements of norm 1 with respect to the 2-norm $\|\|\cdot\|\|_2$, while the input and outputs have the same p-norm for other odd p’s. On the other hand, $a$ sends an odd number $x$ to an element of 2-norm strictly smaller that $1$, i.e. if $x$ is odd then we have $\|\|x\|\|=1$ and $\|\|a(x)\|\| < 1$. However, $a$ behaves the same way as $b$ in terms of other p-norms: it preserves p-norms for p different than 2.

A geometric analogy and p-norms of the elements in the sequence

I will give a similar example but from the realm of geometry: take the set of complex numbers and the complex norm. Fix a real number $\epsilon \> 1$. Define a recursive sequence on the set of elements of norm 1 (the complex unit circle) as follows: let $x_0\in S^1$, and let \[ x_{n+1} = \frac{x_n + \epsilon}{\|x_n + \epsilon\|} \] Then this sequence stabilizes at 1 for every starting point $x_0\in S^1$. In this example $a(x)$ is analogous to $x\mapsto x+\epsilon$ and $b(x)$ is analogous to $x\mapsto x/\|x\|$. The proof of the fact that all sequences stabilize is straight-forward once one realizes that there is an inequality of the form \[ d(x_{n+1},1) \leq \frac{d(x_n,1)}{2} \] for every $n$ and starting value $x_0\in S^1$ where $d(x,y)$ is the geodesic distance on $S^1$ (fancy word for we measure the angle between the points $x$ and $y$ on the unit circle)

So, it is a good idea to check to see if there is a pattern in the p-norms of the elements appearing in the recursive sequence $x_{n+1} = ab(x_n)$ and $y_{n+1} = ba(y_n)$ for any starting point $x_0\in\mathbb{Z}$ and $y_0\in\mathbb{Z}$.

An experiment

I need to measure the 2-part of a positive integer. I will write a more generic function to measure the p-part of an integer:

(defun p-part (n p)
   (cond ((zerop n) nil)
         ((< n 0) (p-part (- n) p))
         (t (do ((c 0 (1+ c))
                 (m n (/ m p)))
                ((not (zerop (mod m p))) c)))))

P-PART

(defun two-part (n) (p-part n 2))

TWO-PART

Let me test

(mapcar 'two-part (loop for i from -2 to 8 collect i))

(1 0 NIL 0 1 0 2 0 1 0 3)

Next, the two pieces $a$ and $b$:

(defun a(n) 
   (if (equal n 1)
       1
       (1+ (* 3 n))))

A

(defun b(n)
   (if (evenp n)
       (b (/ n 2))
       n))

B

and the iterator function which iterates the sequence until it hits a cycle:

(defun iterate-collatz-ab(x)
   (let ((res))
      (do ((y x (a (b y))))
          ((member y res) (nreverse res))
        (push y res))))

ITERATE-COLLATZ-AB

(defun iterate-collatz-ba(x)
   (let ((res))
      (do ((y x (b (a y))))
          ((member y res) (nreverse res))
        (push y res))))

ITERATE-COLLATZ-BA

Let me test

(defvar *test-case-ab* (iterate-collatz-ab (+ 11 (random 22391))))

*TEST-CASE-AB*

*test-case-ab*

(8068 6052 4540 3406 5110 7666 11500 8626 12940 9706 14560 1366 2050 3076
 2308 1732 1300 976 184 70 106 160 16 1)

(defvar *test-case-ba* (iterate-collatz-ba (+ 11 (random 22391))))

*TEST-CASE-BA*

*test-case-ba*

(13623 20435 30653 11495 17243 25865 19399 29099 43649 32737 24553 18415
 27623 41435 62153 46615 69923 104885 9833 7375 11063 16595 24893 9335
 14003 21005 7877 1477 277 13 5 1)

and check their p-parts for $p=2$, $p=3$ and $p=5$.

(mapcar 'two-part *test-case-ab*)

(2 2 2 1 1 1 2 1 2 1 5 1 1 2 2 2 2 4 3 1 1 5 4 0)

(mapcar (lambda (x) (p-part x 3)) *test-case-ab*)

(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

(mapcar (lambda (x) (p-part x 5)) *test-case-ab*)

(0 0 1 0 1 0 3 0 1 0 1 0 2 0 0 0 2 0 0 1 0 1 0 0)

(mapcar (lambda (x) (p-part x 7)) *test-case-ab*)

(0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0)

(mapcar 'two-part *test-case-ba*)

(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

(mapcar (lambda (x) (p-part x 3)) *test-case-ba*)

(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

(mapcar (lambda (x) (p-part x 5)) *test-case-ba*)

(0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 3 0 1 0 1 0 1 0 0 0 0 1 0)

(mapcar (lambda (x) (p-part x 7)) *test-case-ba*)

(0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0)

Discussion