The Collatz Conjecture: the simple math problem we still can’t solve

Someone recently asked GPT-3 to solve the collatz conjecture. The AI wasn't too optimistic...

https://philosopherai.com/philosopher/solve-the-collatz-conj...

Sketch:

Consider a large r-bit random number. The expectation of the number of zeros at the end of the number is \Sum_i=1^n[2^-i]=1-2^-r. If the number is even, the expectation is 2-2^-r, so, the size will be reduced by that number of bits. If it is odd, the number of bits will be increased in expectation by ~ln2(3), and the result is guaranteed to be even. So, in the random case with r>2, the result is an expected loss of bits.

Now let's try to make the randomized problem into something that more closely resembles the original problem. Replace 3n+1 with 3n+m, where m is a random number. The condition for the randomized recurrence to collapse is that m has less than p=1+(2-ln2(3)-2^-r)*r-1 bits, and the last bit is always 1. Note that this m only guarantees 2-2^-p ending zeros in expectation for even numbers, and the remainder comes from the original selection.

Partition any r-bit number into an r-p-bit and a p-bit number, where r-p>ln2(3)+p, and with random m, the cases become, even, reduce by 2-2^-p bits, odd, add some amount less than that of random bits. Decrease bits in expectation each recursion, and the randomness guarantees that this will happen (central limit etc).

Now if you believe that the proof of the randomized problem is valid when r is reduced to where p=1, and of course we can show this for all such numbers, then we're done.

If you don't, then we need to deconstruct m. We know that it works for m=1 for some bound on r, and we know that it works for random m<2^p for unbounded r. Somehow we have to get to m=1 for unbounded r. So split the problem as before, and take the number of odd numbers encountered in the bounded case to be greater than r/ln2(3), as this is otherwise trivial because bits will never increase beyond r. Then this resulting value must also be one of these cases, and so on, and so on, which implies a cycle in the bits beneath the bound.

Back to m. It's probably trivial to show that the problem favors bit reduction as the random bits in m decrease. 1 is just zero random bits. There's an induction somewhere in there...

Okay, I have a few more ideas, but I'm sure none of this is new, and I know nothing about this problem aside from the introduction to this article, so that's about all the mental mastication I have time for today. Thanks HN for humoring me.

A friend of mine wrote a simple program to try to evaluate the Collatz Conjecture on my electromechanical computer! http://www.chrisfenton.com/the-numbotron/

I like more the Lychrel problem (196). I think it is somehow connected to halting problem, and is not provable.

The problem seems to preclude any number reaching 0, so how would you conceivably ever break the loop?

Looks like halting problem.

The article is a description of the Collatz conjecture, but little on the title.