I recently decided to look into the problem for fun, and I came across a pathway to a proof, and, though it's rather long, I was wondering if it has been investigated before.
So, for the Collatz Conjecture, to prove it, we just need to prove that applying the corresponding operation to every number, $3x+1$ if odd and $\frac{x}{2}$ if even, then they would eventually reach a number smaller than it. Here's how I went at it, and to me, it seems like a feasible path to take.
Operations
For simplicity, I will define the operation of $3x+1$ to be $m$ and $\frac{x}{2}$ to be $d$, standing for multiplication and division. Take that for a number like 5, the combination of operations that would lead to a smaller number would be $\{m, d, d\}$ as $5 \xrightarrow{m} 16 \xrightarrow{d} 8 \xrightarrow{d} 4$.
My Approach
What I realized was that each set of operations would just correspond to a linear equation. For example, $\{m, d, m, d, d, d\}$ would just be $\frac{3(\frac{3x+1}{2})+1}{8} = \frac{9}{16}x + \frac{5}{16}$. The key is that if there is a whole number that satisfies the equation, like $x=3$, then every 16 whole numbers, there would be another number that when undergoing the same set of operations, it would reach a smaller resulting value. This is because the slope is a fraction with the denominator equal to 16.
For example, $3 \xrightarrow{m} 10 \xrightarrow{d} 5 \xrightarrow{m} 16 \xrightarrow{d} 8 \xrightarrow{d} 4 \xrightarrow{d} 2$. This should work for $3+16=19$ which is true: $19 \xrightarrow{m} 58 \xrightarrow{d} 29 \xrightarrow{m} 88 \xrightarrow{d} 44 \xrightarrow{d} 22 \xrightarrow{d} 11$. In general, this set of operators corresponds to the set of positive integers in $16n+3$. The reason 16 is the leading coefficient is because 4 $d$ operations were used, accounting for the $2^4 = 16$ on the denominator of the slope of the corresponding linear function generated by this set of operations.
So, each valid set of operations would work for a specific set of numbers which would be equally spaced by two to the power of the number of times the $d$ operation is used (i.e. as we said $\{m, d, m, d, d, d\}$ works for all $16n + 3$ numbers). Now, if we can construct all the valid set of operators and prove that combining all their corresponding set of integers that they work on would cover all odd integers, then that would prove the conjecture.
Creating These Sets of Operators
The most basic case is $\{m, d, d\}$, and by not too much difficulty, these cover all the $4n+1$ numbers. We can then move on to $8n+k$ numbers. This would require 3 $d$ operations. However, $\{m, d, d, d\}$ doesn't work because it essentially repeats the case of $\{m, d, d\}$ and we're trying to create a new set of integers. For example, $\{m, d, d, d\}$ more specifically works for all $8n + 5$ numbers, but those are contained within $4n+1$. We also can't consider using 2 $m$ operators as then the slope of the resultant linear function would be $\frac{9}{8}$ and at the end of the string of operations, any number would not turn into a smaller one.
We can then move on to the set of $16n + k$, and we realize only $\{m, d, m, d, d, d \}$ procudes a unique set of integers $16n + 3$ which isn't previously contained within $4n+1$. We can continue, but for clarity, below are some rules:
Rules for the Sets of Operators
-
If starting with any number, applying the operators in sequencial order will only result in a smaller number with the last operator, not in the middle. Otherwise, the resulting set of valid integers would be contained in another set of integers derived from a smaller set of operators (like $8n+5$ in $4n+1$).
-
Like the Collatz Conjecture, $d$ must come after an $m$ operator and each set must start with $m$ as we are dealing with odd numbers.
-
As a rule of thumb, if M is the number of $m$ operators and D is the number of $d$ operators, $3^M < 2^D < 3^{M+1}$ to ensure the operator set can turn an integer into a smaller one (i.e. applying $3x+1$ too many times doesn't give us what we want; the slope of the reduced linear function as descibed above must have a slope < 1).
More Sets of Operators
We can continue to $32n + k$. Here, there are two possibilities: $\{m, d, m, d, m, d, d, d\}$ and $\{m, d, m, d, d, m, d, d\}$ corresponding to the unique set of integers $32n+23$ and $32n+11$. We can continue on to larger sets, but I decided to code it. Note that there often are gaps between the powers of two because sometimes the $3^M < 2^D < 3^{M+1}$ isn't satisfied with equal increments of the number of $m$ and $d$ operators as $3^x$ grows faster than $2^x$.
With $64n + k$ numbers, similar to the $8n+k$ numbers, there aren't new operator sets that can work on these numbers as the number of $m$ operators remain as 3 which would mean it would overlap with $32n + k$ numbers. Therefore, any set of operators producing integers belonging to $64n+k$ are not new ones, so no new sets of operators work. This will often appear in later sequences.
Here, we will generalize with a table below. Many of the lower values I derived from coding this problem. $c_k$ is the number of possible sets of operators the can operate on integers with the general form on the left of each kth row:
\begin{array}{|c|c|c|c|}
\hline
\text{Set of Integers} & \text{Number of Possible Corresponsing Sets of Operators (}c_k\text{)} \\ \hline
4n+k & 1 \\ \hline
8n+k & 0 \\ \hline
16n+k & 1 \\ \hline
32n+k & 2 \\ \hline
64n+k & 0 \\ \hline
128n+k & 3 \\ \hline
256n+k & 7 \\ \hline
512n+k & 0 \\ \hline
1024n+k & 12 \\ \hline
2^{11}n+k & 0 \\ \hline
2^{12}n+k & 30 \\ \hline
2^{13}n+k & 85 \\ \hline
2^{14}n+k & 0 \\ \hline
2^{15}n+k & 173 \\ \hline
2^{16}n+k & 476 \\ \hline
2^{17}n+k & 0 \\ \hline
2^{18}n+k & 961 \\ \hline
2^{19}n+k & 0 \\ \hline
2^{20}n+k & 2652 \\ \hline
2^{21}n+k & 8045 \\ \hline
2^{22}n+k & 0 \\ \hline
2^{23}n+k & 17637 \\ \hline
2^{24}n+k & 51033 \\ \hline
2^{25}n+k & 0 \\ \hline
2^{26}n+k & 108950 \\ \hline
2^{27}n+k & 312455 \\ \hline
2^{28}n+k & 0 \\ \hline
2^{29}n+k & 663535 \\ \hline
2^{30}n+k & 0 \\ \hline
2^{31}n+k & 1900470 \\ \hline
2^{32}n+k & 5936673 \\ \hline
2^{33}n+k & 0 \\ \hline
2^{34}n+k & 13472276 \\ \hline
2^{35}n+k & 39993895 \\ \hline
\end{array}
This was as far as my computer could handle. If the Collatz Conjecture is true, then if we continue this, all the possible sets of integers resulting from all the possible valid sets of operators $m$ and $d$ must represent all $2n+1$ numbers of just all odd numbers. This would mean that all the possible valid combinations of operators will cause every odd number to eventually dip below it's orginal value in the Collatz sequence. One way to think of it is that it's similar to the $\frac{1}{4} + \frac{1}{8} + \frac{1}{16} … = \frac{1}{2}$. However, in this case, each fraction of a power of 2 has coeffiecients, some being 0.
My Conclusions and Question
In our case, we want $c_1\cdot\frac{1}{4} + c_2\cdot\frac{1}{8} + c_3\cdot\frac{1}{16} + … = \frac{1}{2}$. Or in other words,
$$\sum_{k=1}^{\infty} \frac{c_k}{2^{k+1}} = \frac{1}{2}$$
So far, as my computer can handle, I can get up to 34 terms. It can also manually be done by using the values in the table:
$$\sum_{k=1}^{34} \frac{c_k}{2^{k+1}} = 0.492321204$$
The issue is, I can't find a general pattern, but it really does seem to converge to $\frac{1}{2}$, which would, as it seem, prove the conjecture.
After this long desciption, I have been wondering has this been done before? If so, is there a pattern to connect $c_k$ and $2^{k+1}$?
Best Answer
Terras already shown that the density of the set of numbers reaching a lower value than itself is 1 here: http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf (an other post on density here: What fraction of all $\mathbb{N}$ are powers of 2? )
He also shown the periodicity mod $2^D$, and your {m,d} encoding is the parity vector which he calls "encoding representation". He worked with the "condensed" version ($\frac{3x+1}{2}$ and $\frac{x}{2}$)
So, we usually use this sequence instead : https://oeis.org/A100982
It is used in optimized Collatz sieves (see comments here Calculate the maximum in the Collatz sequence and especially here http://www.ericr.nl/wondrous/techpage.html)
Note that it wouldn't solve Collatz conjecture since it doesn't address any of the 2 main points: No cycles, No divergent trajectories.
An other post that might interest you (about the set $\{4k+1, 16k+3, 32k+23, 128k+15, 256k+95, 1024k+575, 4096k+383... \}$ for the special case of V-inverted sequences)
Showing $3^iq-2^{i-p}\neq2^pq-1$, with $p:=\lceil i\,\log_23\rceil$, $q:=\left\{\frac{2^{i}\,3^{2^{p-i-2}}}{2^p3^i}\right\}$, $i>6$
(and you can find a tree of it made by Mike W. here page 13 https://arxiv.org/pdf/1709.03385.pdf)