I've been thinking about the possibility of a divergent collatz sequence for the Collatz Conjecture. In other words, the possibility that neither a trivial nor non-trivial cycle is ever reached.
If any collatz sequence diverges, there must be a least integer that gives rise to such a divergent series.
It seems to me that it is straight forward to find conditions for when an integer cannot be the least integer that gives rise to a divergent collatz sequence.
Let:
- $\nu_2(x)$ be the 2-adic valuation of $x$
- $T_0(x) = x$
- $T_{n+1}(x) = \dfrac{3T_n(x)+1}{2^{\nu_2(3T_n(x)+1)}}$
- $u\ge 0, v > 0$ be integers
Does it now follow that the following odd integers cannot be the least integer that gives rise to a divergent collatz sequence (assuming that one occurs):
- $4u+1$
- $6v-1$
- $4^v-1$
- $2^{6u+5}-1$
Here's my reasoning:
(1) $T_1(4u+1) < 4u+1$ since:
$$T_1(4u+1) \le 3u+1 = \dfrac{12u+4}{4} < 4u+1$$
(2) $4v – 1 < T_1(4v-1) = \dfrac{12v-2}{2} = 6v – 1$ so if $6v-1$ leads to a divergent, collatz sequence, so does $4v-1$.
(3) $4^v-1$ since:
-
From details here:
-
$T_{2v-2}(2^{2v-1}-1) = 2\times3^{2v-2}-1 =4\left(\dfrac{3^{2v-2}-1}{2}\right)+1$
-
$T_{2v-1}(2^{2v}-1) = 2\times3^{2v-1}-1 =4\left(\dfrac{3^{2v-1}-1}{2}\right)+1$
-
-
$\dfrac{3^{2v-1}-1}{2}$ is odd since:
$$3^{2v-1} -1 \equiv (-1)^{2v-1} – 1 \equiv 2 \pmod 4$$
- From details here:
$$T_1\left(4\left(\dfrac{3^{2v-2}-1}{2}\right)+1\right) = 3\left(\dfrac{3^{2v-2}-1}{2}\right) +1= \left(\dfrac{3^{2v-1}-1}{2}\right)$$
$$T_1\left(4\left(\dfrac{3^{2v-1}-1}{2}\right)+1\right) = T_1\left(\dfrac{3^{2v-2}-1}{2}\right)$$
- So, if $4^v-1$ leads to a divergent collatz sequence, so does $2^{2v-1}-1$
(4) $2^{6u+5}-1$ since:
-
if $x \equiv 4 \pmod 9$, then there exists an integer $u > 0$ with $T_2(u) = x$ and $u < x$
- Assume $x \equiv 4 \pmod 9$ so that there exists an integer $t$ such that $x = 9t+4$
- $\dfrac{4x-1}{3} = \dfrac{4(9t+4)-1}{3} = \dfrac{36t + 15}{3} = 12t + 5$ which is an odd integer.
- $\dfrac{2(12t+5)-1}{3} = \dfrac{24t+9}{3} = 8t+3$ which is an odd integer.
- Clearly, $8t+3 < 9t+4$
- $T_2(8t+3) = \dfrac{3\left(\frac{3(8t+3)+1}{2}\right)+1}{4} = \dfrac{3(12t+5)+1}{4} = 9t+4$
-
$2^{6u+5}-1 \equiv (-1)(4)(-1)^{2u} – 1 \equiv -5 \equiv 4 \pmod 9$
Is my reasoning for these conditions valid? Did I miss any other elementary conditions?
Best Answer
This is intended as a comment, but too long for the comment-field
A simple table gives infinite modular classes of odd numbers $a_1$, which always decrease by one step of the $(3x+1)/\nu_2(3x+1)$ iteration to $a_2$. This is, with $k \in \{0,1,2,3,...\}$:
Table 1: $$ \begin{array}{r|r|r||r|r|r} A &a_1 &a_2&& A & a_1 & a_2\\ \hline \color{red} {1} & \color{red} { 2^1\cdot 2k+3\phantom {1}} & \color{red} {3\cdot 2k+5} && \color{green} {2}& \color{green} {2^2\cdot 2k+1 \phantom {1}} &\color{green} { 3\cdot 2k+1} \\ 3 & 2^3\cdot 2k+13 & 3\cdot 2k+5 && 4& 2^4\cdot 2k+5 \phantom {1} & 3\cdot 2k+1 \\ 5 & 2^5\cdot 2k+53 & 3\cdot 2k+5 && 6& 2^6\cdot 2k+21 & 3\cdot 2k+1 \\ \vdots & \vdots &\vdots && \vdots &\vdots & \vdots & \\ A & 2^A\cdot 2k+r_A & 3\cdot 2k+5 && A& 2^A\cdot 2k+r_A & 3\cdot 2k+1 \\ \vdots & \vdots &\vdots && \vdots &\vdots & \vdots & \\ \end{array}$$ where $r_A = { 2^A-1\over 3}$ if $A$ is even, and $r_A = { 5 \cdot 2^A-1\over 3}$ if $A$ is odd.
From this table it is easily visible, that
This shows that the least element $a_1$ of a divergent sequence must be of the form $4k+3$ .
Out of couriosity I've tried to tabular the subforms of $a_1=4k+3$ in a comparable way($ b_1=16k+3$ and $c_k=16k+11$ and so on) to pinpoint the distinction between increasing and decreasing iterations - but this leads soon to another representation scheme, which becomes more complicated. (And I've not yet put that together in a nicely-readable essay.)
update: I see that the list (or better:tree) that I've created for this aspect is just that list, that user @Vepier mentions in his/her comment.
The beginning of this list, ordered for the powers-of-2 in the $a_1$ variable, looks like this. It is a systematic list of modular classes for $a_1$ which are decreasing after a small number $n$ of iterations (here $n$ is also the length of the exponents-vector $E$). The exponents-vector $E$ (here printed as compacted string) of the exponents $A_1,A_2,A_3,...A_n$ for "dropping time" $n$ is generated by a recursive tree structure.
Table 2:
The still increasing (and so hopefully diverging) cases are that where the last entry in $E$ is smaller than the shown one.
Here is a table, where in the above list I measure the covering of the odd numbers in residue-classes sequentially up to a given residue class. From this I calculate the relative number of residue classes not covered so far, which means, that part of a residue-class whose members $a_1$ increase after that $n$ steps. Over the residueclasses we find, that the number of those potential divergent $a_1$ decreases with $n$ (P.s.: this is just barely observation and no final interpretation so far):
Table 3: