(Collatz) Modulo 18 Partitions of Collatz 3n+1 Trajectories

Question

I have examined partial Collatz 3n+1 trajectories going from one odd integer to the next. These lead to an infinite number of repeated patterns where the "next" odd integer is congruent to one of only six patterns: {5, 11, 17, 1, 7 or 3} mod 18. As was pointed out by Mirko in an earlier comment, these are the only possible Collatz results for mod 18, so it may seem trivial, but what I found interesting was a rotation pattern in the transformations, which I will try to illustrate rather than formally define.

The patterns resulting in {5, 11, 17} (mod 18) are shown in the table below; the cycle repeats every third even level, so $A_0$ and $A_6$ reach {5, 11, 17} from the same starting points {3,1,5} (mod 6).

$$ \begin{array} {|c|cc|cc|cc|cc|} \hline SET & INPUT & MOD & TRANSFORM & MOD & INPUT MOD 6 & TRANSFORM MOD 6 \\ \hline \cdots & 3 & 12 & 5 & 18 & 3 & 5 \\ A_0 & 7 & 12 & 11 & 18 & 1 & 5 \\ \cdots & 11 & 12 & 17 & 18 & 5 & 5 \\ \hline \cdots & 13 & 48 & 5 & 18 & 1 & 5 \\ A_2 & 29 &48 &11 & 18 &5 & 5 \\ \cdots & 45 & 48 & 17 & 18 &3 & 5 \\ \hline \cdots & 53 & 192 &5 & 18 & 5 & 5 \\ A_4 & 117 &192 & 11 & 18 &3 &5 \\ \cdots & 181 & 192& 17 &18 &1 &5 \\ \hline \cdots & 213 & 768 & 5 & 18 &3 & 5 \\ A_6 & 469 &768 & 11 & 18 & 1 & 5 \\ \cdots &725 & 768 & 17 & 18 & 5 & 5 \\ \hline \end{array} $$

Similarly, the patterns resulting in {1, 7, 13} (mod 18) are shown in the table below; the cycle repeats every third odd level, so $A_1$ and $A_7$ reach {1, 7, 13} from the same starting points {1,3,5} (mod 6).

$$ \begin{array} {|c|cc|cc|cc|cc|} \hline SET & INPUT & MOD & TRANSFORM & MOD & INPUT MOD 6 & TRANSFORM MOD 6 \\ \hline \cdots & 1 & 24 & 1 & 18 & 1 & 1 \\ A_1 & 9 & 24 & 7 & 18 & 3 & 1 \\ \cdots & 17 & 24 & 13 & 18 & 5 & 1 \\ \hline \cdots & 5 & 96 & 1 & 18 & 5 & 1 \\ A_3 & 37 & 96 & 7 & 18 & 1 & 1 \\ \cdots & 69 & 96 & 13 & 18 & 3 & 1 \\ \hline \cdots & 21 & 384 & 1 & 18 & 3 & 1 \\ A_5 & 149 & 384 & 7 & 18 & 5 & 1 \\ \cdots & 277 & 384 & 13 & 18 & 1 & 1 \\ \hline \cdots & 85 &1536 & 1 & 18 & 1 & 1 \\ A_7 & 597 & 1536 & 7 & 18 & 3 & 1 \\ \cdots & 1109 & 1536 & 13 & 18 & 5 & 1 \\ \hline \end{array} $$

QUESTION: Are these observed patterns useful in attacking the Collatz 3N+1 problem?

OBSERVATIONS:

(1) The path among the first members of each partition is given by: $$7 => 11 => 17 => 13 => 5 => 1$$

(2) There is a one-step path to each of them from $\left(3\;mod\;6 \right)$ $$3=>5\;;9=>7\;;21=>1\;;45=>17\;;69=>13\;;117=>11$$

(3) Applying the Collatz transformations a second time to the six partitions shows that the Collatz transformations map these partitions among themselves. A portion of this mapping is show below. $$ \begin{array} {|c|c|c|c|} \hline FROM & SECOND & EQUIVALENT & FROM \\ PARTITION & TRANSFORM & TRANSFORM & SET \\ \hline 11 mod 18 & 11 mod 36 => 17 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ 5 mod 18 & 23 mod 36 => 35 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ 17 mod 18 & 35 mod 36 => 53 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ \hline 7 mod 18 & 7 mod 36 => 11 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ 1 mod 18 & 19 mod 36 => 29 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ 13 mod 18 & 31 mod 36 => 47 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ \hline 1 mod 18 & 1 mod 72 => 1 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ 7 mod 18 & 25 mod 72 => 19 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ 13 mod 18 & 49 mod 72 => 37 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ \hline 17 mod 18 & 17 mod 72 => 13 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ 5 mod 18 & 41 mod 72 => 31 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ 11 mod 18 & 65 mod 72 => 49 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ \hline 11 mod 18 & 29 mod 144 => 11 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ 5 mod 18 & 77 mod 144 => 29 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ 17 mod 18 & 125 mod 144 => 47 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ \hline 13 mod 18 & 13 mod 144 => 13 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ 7 mod 18 & 61 mod 144 => 31 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ 1 mod 18 & 109 mod 144 => 49 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ \hline 5 mod 18 & 5 mod 288 => 1 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ 11 mod 18 & 101 mod 288 => 19 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ 17 mod 18 & 197 mod 288 => 37 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ \hline 1 mod 18 & 37 mod 288 => 7 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ 7 mod 18 & 133 mod 288 => 25 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ 13 mod 18 & 229 mod 288 => 43 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ \hline \end{array} $$

(4) So, after the first Collatz iteration removes multiples of three, the transformations in remaining iterations all work from the same set of six modulo 18 partitions and until studied further, this lends no particular insight into whether a particular sequence will cycle, diverge or revert to 1.

(5) The second iteration, sorted by source partition ...

$$ \begin{array} {|c|c|c|c|} \hline FROM & SECOND & SUBSET \; OF & FROM \\ PARTITION & TRANSFORM & TRANSFORM & SET \\ \hline 1 mod 18 & 19 mod 36 => 29 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ 1 mod 18 & 1 mod 72 => 1 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ 1 mod 18 & 109 mod 144 => 49 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ 1 mod 18 & 37 mod 288 => 7 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ 1 mod 18 & 181 mod 576 => 17 mod 54 & 181 mod 192 => 17 mod 18 & A_{4} \\ 1 mod 18 & 1045 mod 1152 => 49 mod 54 & 277 mod 384 => 13 mod 18 & A_{5} \\ \hline 5 mod 18 & 23 mod 36 => 35 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ 5 mod 18 & 41 mod 72 => 31 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ 5 mod 18 & 77 mod 144 => 29 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ 5 mod 18 & 5 mod 288 => 1 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ 5 mod 18 & 437 mod 576 => 41 mod 54 & 53 mod 192 => 5 mod 18 & A_{4} \\ 5 mod 18 & 149 mod 1152 => 7 mod 54 & 149 mod 384 = > 7 mod 18 & A_{5} \\ \hline 7 mod 18 & 7 mod 36 => 11 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ 7 mod 18 & 25 mod 72 => 19 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ 7 mod 18 & 61 mod 144 => 31 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ 7 mod 18 & 133 mod 288 => 25 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ 7 mod 18 & 565 mod 576 => 53 mod 54 & 181 mod 192 => 17 mod 18 & A_{4} \\ 7 mod 18 & 277 mod 1152 => 13 mod 54 & 277 mod 384 => 13 mod 18 & A_{5} \\ \hline 11 mod 18 & 11 mod 36 => 17 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ 11 mod 18 & 65 mod 72 => 49 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ 11 mod 18 & 29 mod 144 => 11 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ 11 mod 18 & 101 mod 288 => 19 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ 11 mod 18 & 245 mod 576 => 23 mod 54 & 53 mod 192 => 17 mod 18 & A_{4} \\ 11 mod 18 & 533 mod 1152 => 25 mod 54 & 149 mod 384 = > 7 mod 18 & A_{5} \\ \hline 13 mod 18 & 31 mod 36 => 47 mod 54 & 7 mod 12 => 11 mod 18 & A_{0} \\ 13 mod 18 & 49 mod 72 => 37 mod 54 & 1 mod 24 => 1 mod 18 & A_{1} \\ 13 mod 18 & 13 mod 144 => 5 mod 54 & 13 mod 48 => 5 mod 18 & A_{2} \\ 13 mod 18 & 229 mod 288 => 43 mod 54 & 37 mod 96 => 7 mod 18 & A_{3} \\ 13 mod 18 & 373 mod 576 => 35 mod 54 & 181 mod 192 => 17 mod 18 & A_{4} \\ 13 mod 18 & 661 mod 1152 => 31 mod 54 & 277 mod 384 => 13 mod 18 & A_{5} \\ \hline 17 mod 18 & 35 mod 36 => 53 mod 54 & 11 mod 12 => 17 mod 18 & A_{0} \\ 17 mod 18 & 17 mod 72 => 13 mod 54 & 17 mod 24 => 13 mod 18 & A_{1} \\ 17 mod 18 & 125 mod 144 => 47 mod 54 & 29 mod 48 => 11 mod 18 & A_{2} \\ 17 mod 18 & 197 mod 288 => 37 mod 54 & 5 mod 96 =>1 mod 18 & A_{3} \\ 17 mod 18 & 53 mod 576 => 17 mod 54 & 53 mod 192 => 17 mod 18 & A_{4} \\ 17 mod 18 & 917 mod 1152 => 43 mod 54 & 149 mod 384 = > 7 mod 18 & A_{5} \\ \hline \end{array} $$

Answer 1

Okay, so I can finally see something of interest (to me) in this exercise. The formula for the transformation of an odd integer to the next odd integer is related to the partition in which that next odd integer resides. If $n_0$ represents any odd integer which starts a sequence representing the odd numbers only in a Collatz 3n+1 sequence, the formula for $n_1$ is given by.

$$ n_1 = (3n_0 + 1) / {\left(2^k\right)} $$ $$ \;for\; some\; k \in N $$ $$ where \; k \cong \left(1\;mod\;2\right) \equiv n_1 \cong \left(5\;mod\;6\right) $$ $$ and \; where \; k \cong \left(0\;mod\;2\right) \equiv n_1 \cong \left(1\;mod\;6\right). $$

The significance is this that $$ \left(n_1 \gt n_0 \iff k=1\right) \implies \left(n_1 \gt n_0 \implies n_1 \cong \left(5 \; mod \; 6\right) \right) $$

So we can focus on (5 mod 6) to look for divergence behavior.

Answer 2

5 mod 6 is the same as -1 mod 6. A number satisfying that would be a number of the form (2)(3)z-1 where z is a (nonnegative) integer. Such a number is the image by the transformation T(x) = (3x+1)/2 of the number x = (2)(2)z-1.

Consider "runs" of consecutive odd iterates of T. If you have more factors 3 in z, you can go "back" (and down) further in the same "run" by replacing (some of) these 3's by 2's. If you have more factors 2 in z, you can go "forward" (and up) further in the same "run" by replacing (some of) these 2's by 3's.

Any odd x can be written x = (2^n)u-1 with u odd. Then if T is iterated starting from x, the (n-1)-th iteration will give the last consecutive odd number in the sequence, and that will be of the form 1+4k. (The n-th iteration will give an even number.) You could call this sequence of n odd values (that includes x) a "run" starting from x. If u has some factors 3, replacing those by 2's one by one will produce "precedents" to x, until there are no more factors 3. The last (and smallest) number obtained this way starts the maximal run that contains x. That maximal run is uniquely identified by its last and highest point 1+4k, or its "label" k.

Eventually, each odd (nonnegative) integer can be put in exactly one maximal (but finite) "run". Any two such maximal runs are either the same or disjoint. If they are disjoint, they might "communicate" (in one or more "jump" step), or not. (This is as far as I got.)

Answer 3

The patterns resulting in $\{1, 7, 13\} \pmod {18}$ can be explained if you view these results in mod $9$. All odd $n$ under function $3n+1$ iterate to $1$, $7$, or $4 \pmod 9$. I believe this pattern is non-trivial.