I also identify very closely with Rex here! I feel like we'd get along. Collatz conjecture always drive me mad when I'm doing a big number though, not very good at multiplying by three, I've been playing with it looking for patterns for a few months now (unsurprisingly, making no progress on the problem that stumped Erdos, but it's always fun to try).
Here's where I'm at. If the Collatz Conjecture is false, then there is at least one number which:
a) Increases infinitely. I haven't made any headway on proving that such a number exists or proving that such a number can't exist.
Or
b) Forms a loop, such that following the operations of the Collatz Conjecture returns to that number. If such a loop exists (aside from the 1-4-2-1 loop), there must be a smallest number. I've tried finding the smallest number in a loop through this:
Express the starting number and ending number as: Start => End.
Given 5, one would see that we get 5 => 16 => 8 => 4. I'll stop there, since 4 < 5, 5 cannot be the lowest number in a loop. I represent this as 5 => 4.
Now, I start with the set of all natural numbers being:
x => x
Right away, I need to know if x is odd or even, so I split it into two cases:
1) 2x => 2x, which reduces to 2x => x and since I get a result less than the original, it is
resolved. That is, this shows that every even number reduces to a number less than itself under the Collatz Conjecture.
2) 2x + 1 => 2x + 1. I multiply the right-hand side (the
result) by 3 and add 1 to get 2x + 1 => 6x + 4. Since both numbers on the right are even, I can divide the result by 2 to get: 2x + 1 => 3x + 2.
This leaves one unresolved case:
2x + 1 => 3x + 2. I can't know if 3x + 2 is odd or even until I know whether x is odd or even, so I must split it again:
1) 4x + 1 => 6x +2, which becomes 4x + 1 => 3x + 1, and is resolved. Note that this means that every number that is of the form 4x + 1, where x >= 1 (5, 9, 13, 17, 21, ...) reduces to a number less than itself after 3 steps. This also contains the special case where x = 0 and 1 => 1 after 3 steps. That's the 1-4-2-1 loop mentioned above. But after just this much work, we have eliminated 25% of all numbers from being part of a loop.
2) 4x + 3 => 6x + 5, which becomes 4x + 3 => 9x + 8. This is unresolved and need to be split yet again.
We can go on like this forever. I've proven that you will never reach a point where all cases are resolved, because for any number of steps you choose, there is a number that requires that many steps to reduce to something less than itself.
But, let's try solving for Start = End. All cases are of the form Ax + B => Cx + D. For Ax + B to be equal to Cx + D, we need:
Ax + B = Cx + D
Ax - Cx = D - B
(A - C)x = (D - B)
x = (D - B) / (A - C)
For this to be a positive number, we need C > A and D < B or we need C < A and D > B.
Now, note that there is a ratio of C/A and a ratio of D/B, such that D/B >= C/A. This follows from the fact that we start with 2x + 1 => 2x + 1 (The single unresolved case after the first split, and in which C = A and D = B). From there, we either divide by 2, which halves both C/A and D/B, so that if D/B >= C/A before dividing then D/B >= C/A after dividing. Or, we multiply by 3 and add 1, in which case C is multiplied by 3, but D is multiplied by 3 and has 1 added to it, so that D/B > C/A. Since D/B >= C/A in all cases, it's impossible to have C > A (so that C/A > 1) and D < B (so that D/B < 1).
Thus, the only way for there to be a loop is to find a case where: Ax + B => Cx + D, such that C < A and D > B.
I wrote a program to start with the first case, x => x (represented in the program as 1x + 0 => 1x + 0) and split cases and resolve cases as shown above. The number of unresolved cases increases geometrically, so that after 41 steps my PC ran out of hard drive space but had resolved 12 billion cases. There were no cases at all where C < A and D > B. So, either I didn't test enough cases or there's a rule and a proof in there somewhere that C < A and D > B is impossible.
I haven't found the rule or proof yet. Since all cases resolve to A being a power of 2 and C being a power of 3, I've been looking for a proof that 2^X - 3^Y > F(X), where Y is chosen as the smallest integer value such that 2^X > 3^Y, where F(X) increases with X faster than D would increase with the Collatz operations. This is where I'm stuck.
I also have an idea to perform a targeted search for very (
very very) large numbers that have the highest probability of producing a case where C < A and D > B, but I haven't implemented it yet.
