What are the known rules on the seed that guarantee the Collatz sequence will stop

collatz conjecturefunction-and-relation-compositionmodular arithmetic

I have written some code that searches for counter-examples to the Collatz conjecture. The following fact enables me to accelerate the search.

In the paper "Garner, Lynn – On The Collatz 3n + 1 Algorithm" Garner claims it is "not hard to verfiy" that the following rules hold.

enter image description here

I have spent about a week trying to prove the general version of this result, but have not succeeded. I will define the terms in Garner's paper, and would be grateful for any help.

The Collatz map $c:\mathbb{N}\to\mathbb{N}$ is defined by

$c\left(n\right):=\frac{1}{2}\begin{cases}
3n+1 & n\text{ odd}\\
n & n\text{ even}
\end{cases}$

Given a seed $n\in\mathbb{N}$ the Collatz sequence is defined as $\left\{ c^{p}\left(n\right)\mid p\in\omega\right\}$, where as usual $c^{0}\left(n\right)=n$ and $c^{p+1}\left(n\right)=c\left(c^{p}\left(n\right)\right)$ for all $n\in\mathbb{N}$.

Given any $n\in\mathbb{N}$ the stopping time $\sigma\left(n\right)$ is the smallest $p\in\mathbb{N}$ such that $c^{p}\left(n\right)<n$. If the Collatz conjecture is true every Collatz sequence has a finite stopping time.

I am after the theorem that says something like; Given $n,m\in\mathbb{N}$, $\sigma\left(n\right)=m$ whenever $n\equiv p\mod{2^{q}}$ for $p,q$ with THIS property. My question is what is THIS property?

Best Answer

These numbers come from explicitly writing out the iterates of the Collatz function and seeing, from that, which numbers have which stopping times. If you want to condense the property being discussed, it's as follows: we can compute that $$c^q(x\cdot 2^q+p)=\alpha x + \beta$$ for some integer constants $\alpha$ and $\beta$. If $\alpha < 2^q$, then, for all great enough $n$ equivalent to $p$ mod $2^q$, we will have $c^q(n) < n$ - and we can use this to create the sort of statements in your question.

It's best to illustrate this with an example. To see that the stopping time of $32x + 11$ is $5$ (for the $c$ in the question*), one could calculate: $$c(32x+11) = 48x + 17$$ $$c^2(32x+11) = 72x + 26$$ $$c^3(32x+11) = 36x + 13$$ $$c^4(32x+11) = 54x + 20$$ $$c^5(32x+11) = 27x + 10$$ Where, for $x\geq 0$, it's clear that the first four iterates are greater than the input, and the fifth is less than the input - hence the stopping time is $5$. Note that we cannot compute the sixth iterate, since $27x+10$ could be either even or odd.

You can run a similar sort of calculation to explicitly get the first $q$ iterates of $c$ applied to $2^q\cdot x + p$ for any $p$ as a linear function of $x$ - and doing such a calculation might reveal the stopping time of numbers of that form (as it did in the example I gave).

If you wanted to generate the list they made in the paper, what you can do is calculate this for every possible mod $2$ residue, and note which residues have fixed stopping times. Then, of those residues which did not have fixed stopping times, you can split them into two residue classes mod $4$, and see if any of those have fixed stopping times (now being able to calculate one more iteration in the future). Then, you can split into residues mod $8$ and so on, until you are satisfied. Note that the number of residues remaining mod $2^q$ will grow exponentially (although the proportion of residues lacking a stopping time will decrease towards $0$).

You can be a bit more sophisticated with this, although it's not clear it would be useful for your application. If you fix the parities of the sequence $x, c(x), c^2(x),\ldots, c^{n-1}(x)$, there is a unique equivalence class mod $2^n$ such that $x$ in that class will have a trajectory with the specified parities - for instance, there is some mod $8$ equivalence class such that $x$ is even, $c(x)$ is odd, and $c^2(x)$ is even. You can note that, for $x$ in that class, we must have $c^n(x)=\alpha x + \beta$ for some rational $\alpha$ and $\beta$ - and can explicitly compute $$\alpha = (3/2)^{\text{# of odd steps in trajectory}}\cdot (1/2)^{\text{# of even steps in trajectory}}.$$ This can give the asymptotic results noted in the paper, but is probably not the most efficient way to generate a list of all classes that don't stop after some number of steps.

(*The paper you quote appears to use the version of the Collatz function that takes two steps to go from odd $x$ to $\frac{1}2(3x+1)$, so gets $8$ instead - but it's the same idea with that method, although it works somewhat less elegantly with that slower function)

Related Question