https://en.wikipedia.org/wiki/3x_%2B_1_problem
The sequence of integers generated the accelerated relation $$ f(x) = \left\{ \begin{array} & \frac{3x + 1}{2} & x \text{ odd} & \\ \frac{x}{2} & x \text{ even} \end{array} \right.$$ can be considered a Markov chain where each number in the sequence is a state and the probability of the next state is exactly 1. Encoding the state as a 1-Hot vector we have $$ x_{n} = \left( \begin{array} & 0 & 0 & \cdots & 1 & 0 & \cdots \end{array} \right)^T$$ where the vector is filled with zeros except at the position corresponding to the integer it is encoding where it is 1. The $x_{n}$ is natually a normal vector.
With this notation we can define the relatión between $x_{n}$ and $x_{n+1}$ as $$ x_{n+1} = Ax_{n} $$ where $$ A = \begin{pmatrix} 0 & 1 & 0 & 1 & \cdots \\ 1 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} $$
Theorem
Let $\upsilon_{t}$ be the average value of $x_{n}$ over $t$ steps: $$ \upsilon_{t} = \frac{1}{t} \sum_{s=0}^{t} x_{s}$$.
Then there is a set of eigenvectors $\Pi$ such that $A\pi = \pi$ where $\pi \in \Pi$.
For all $x_{n}$ then $$\pi = \lim_{t \to \infty} \upsilon_{t}$$ and can be interpreted as the stationary probability distribution of the operator A.
Proof
Show that $$\lim_{t \to \infty} \left| A\upsilon_{t} - \upsilon_{t} \right| \to 0$$
Expand as $$\lim_{t \to \infty} \left| \frac{A}{t} \sum_{s=0}^{t} x_{s} - \frac{1}{t} \sum_{s=0}^{t} x_{s} \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| (Ax_{0} + Ax_{1} + \cdots + Ax_{t}) - (x_{0} + x_{0} + \cdots + x_{t}) \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| (x_{1} + x_{2} + \cdots + x_{t+1}) - (x_{0} + x_{0} + \cdots + x_{t}) \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| x_{t+1} - x_{0} \right|$$
But $x_{0}$ and $x_{t+1}$ are one-hot (normal) vectors so their difference can be at most 2. So the limit is satisfied.
Given that in the limit as $t \to \infty$, $\upsilon_{t}$ is the average value of $x_{n}$ then if the number represented by $x_{n}$ is NOT in a cycle then its average value will tend to 0. Similarly values in a cycle will tend to some non-zero value inversely proportional to the length of the cycle.
The Collatz Conjecture is equivalent to requiring that the transition matrix, $A$, have exactly one real eigenvalue with value 1, i.e. the stationary probability distribution, $\pi$, of the transition matrix settles on a single cycle $2 \to 1 \to 2$. To illustrate this we can use a truncated 4x4 transition matrix. We add an additional restraint on the truncated form requiring that states that would otherwise fall outside the truncated state matrix return to themselves. $$ A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$
The eigenvectors of this matrix are:
from sympy import *
init_printing()
A = symbols('A')
A = Matrix([[0,1,0,0], [1,0,0,1], [0,0,1,0], [0,0,0,0]])
A
A.eigenvects()
This transition matrix has two eigenvectors with eigenvalue equal to 1. One corresponds to the stationary distribution $(1,1,0,0)^T$ which is our main cycle $1 \to 2 \to 1$ and the other $(0,0,1,0)^T$ is the artificial cycle introduced by truncation $3 \to 3$.
For larger matrices, say 20x20, the same applies:
array = []
size = 15;
for i in range(1, size+1):
array.append([0]*size)
j = (3*i+1)>>1 if i%2==1 else i>>1
if(j>size): j=i;
array[i-1][j-1] = 1
A = Matrix(array).transpose()
A
A.eigenvects()
This continues to show the main cycle as the first eigenvector (stationary distribution) and cycles also at 15, 17 and 19 where the sequences go out of the range of the array.
Attempting to solve directly we have:
l = symbols('λ')
for i in range(1, size+1):
array[i-1][i-1] += -l;
A = Matrix(array).transpose()
A
A.transpose().QRdecomposition()
--------------------------------------------------------------------------- NotImplementedError Traceback (most recent call last) <ipython-input-26-2db4bc6cf70f> in <module>() ----> 1 A.transpose().QRdecomposition() ~\Anaconda3\lib\site-packages\sympy\matrices\matrices.py in QRdecomposition(self) 3689 if Q[:, j].norm() != 1: 3690 raise NotImplementedError( -> 3691 "Could not normalize the vector %d." % j) 3692 for i in range(j): 3693 R[i, j] = Q[:, i].dot(mat[:, j]) NotImplementedError: Could not normalize the vector 0.
To prove the conjecture we'd have to show that in the limit as the size of the matrix tends to infinity then there should be only 1 eigenvalue of value 1. I don't know how to do that.
One thing we cvan try is to factor the two function matrices into a matrix for even numbers and a matrix for odd numbers. For the even part we can use: $$ A_{even} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} $$ Then, because it has been separated from the odd part, we can apply it any number of times until all even factors of 2 have been removed. $$ A_{even}^\infty = \lim_{n \to \infty} A_{even}^{n} $$
Which will look like this having removed all factors of 2: $$ A_{even}^\infty = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} $$
For the odd part we do something similar with $A_{odd}$. $$ A_{odd} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} $$
Now we can apply both transformations sequentially until we get the final result which should be 1. $$ (A_{odd}A_{even}^\infty)(A_{odd}A_{even}^\infty)(A_{odd}A_{even}^\infty)... = \lim_{n \to \infty} (A_{odd}A_{even}^\infty)^n = = \begin{pmatrix} 1 & 0 & \cdots \\ 0 & 0 & \cdots \\ \vdots & \vdots & \ddots \\ \end{pmatrix} $$
array = []
size = 32;
for i in range(1, size+1):
array.append([0]*size)
j = i if i%2==1 else i>>1
array[i-1][j-1] = 1
A = Matrix(array)
A
The same relations can be expressed in functional form: We take the long-term average of the difference of successive terms such that $$\lim_{t \to \infty} \frac{1}{t} \sum_{s=0}^{t} \left| f(x_{t}) - x_{t} \right| \to 0$$
Expand as $$\lim_{t \to \infty} \frac{1}{t} \left| \sum_{s=0}^{t} f(x_{s}) - \sum_{s=0}^{t} x_{s} \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| (f(x_{0}) + f(x_{1}) + \cdots + f(x_{t})) - (x_{0} + x_{1} + \cdots + x_{t}) \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| (x_{1} + x_{2} + \cdots + x_{t+1}) - (x_{0} + x_{1} + \cdots + x_{t}) \right|$$ $$\lim_{t \to \infty} \frac{1}{t} \left| x_{t+1} - x_{0} \right|$$
(Need to be more rigourous when moving the sum inside the norm. Probably using the triangle inequality.)
Given that in the limit as $t \to \infty$, $x_{t}$ is the average value of $x_{n}$ then if the number represented by $x_{n}$ is NOT in a cycle then its average value will tend to 0. Similarly values in a cycle will tend to some non-zero value inversely proportional to the length of the cycle. For the limit to converge we need $x_{t+1} - x_{0}$ to be a constant so that $$x_{t+1} = \lambda x_{0}$$ Or, equivalently, $$f^{t}(x) = \lambda x$$
Since we are looking for $f^{n}(x) = 1$ for some value of $n$, the Collatz Conjecture is equivalent to requiring that the function, $f^{t}(x)$, have exactly one positive real eigenvalue with value $\lambda$. It must be exactly one because more than one real eigenvalue would imply the existence of other cycles.
For example take the easiest solution where $f(x)$ is always even giving us $f^n(x)=\frac{x}{2^{n}}$. The eigenvalues of this function are $\frac{x}{2^{n}}=\lambda x \to \lambda=\frac{1}{2^{n}}$ proving that there is only one real eigenvalue and since $f^{n}(x) = \lambda x = 1$ we have $x=2^{n}$ as expected.
In the general case $f(x)$ takes the form $f^n(x)=\frac{3^{m}x+\Omega}{2^{n}}$ where $m<n$ and $\Omega$ is some non-linear combination of powers of 2 and 3, i.e. $\displaystyle\sum_{0\le i<n} 2^{k_{i}} 3^{l_{i}}$. The eigenvalues of this function are $\lambda=\frac{3^{m}x+\Omega}{2^nx}$. Setting $\lambda x=1$ we have $x=\frac{2^{n}-\Omega}{3^{m}}$. This must be positive so we require $\Omega<2^{n}$ which gives a condition for possible combinations of 2 and 3 in $\Omega$
If $\lambda$ is an eigenvalue of $f(x)$ then $\frac{1}{\lambda}$ is an eigenvalue of $f^{-1}(x)$, where $$ f^{-1}(x) = \left\{ \begin{array} & \frac{x-1}{3} \\ 2x \end{array} \right.$$ This is useful because it means we can reverse the sequences, starting at $x=1$ and applying $f^{-1}(1)$ in each direction.
In the above simple case for x all even we have $f^{-n}(x) = x_{n}=2^{n}$ with eigenvalues $\lambda=\frac{1}{2^{n}}$ as expected.
Using this method we can tackle the harder cases such as the odd sequence $f^{-n}(8)$ being applied at each stage. The sequence starts at 8 in this case because sequences with lower starting values do not stay within $\mathbb{Z}^{+}$ when applying $\frac{x-1}{3}$.