Computer scientists attempt to corner the Collatz conjecture

> Every time the coin turns out heads, I take half of the money on the table (i.e the total you have left is divided by 2). Every time it turns out to be tails, your money is multiplied by 1.5 (plus a 50 cents bonus). It’s obvious that this game is totally rigged to my advantage as the amount of heads will converge to be similar to the amount of tails, but the loss you incur with each head result (money divided by 2) is larger than the win gained with each tail result (money multiplied by 1.5 + change).

This game has positive expected value, the only problem is risk of ruin if you size your bets too aggressively as a percentage of your chip stack

This type of reasoning only gives you intuition about half the conjecture. The conjecture says two things:

1. No sequence grows bigger and bigger forever; and

2. No sequence gets caught in a loop (except for the trivial 4 -> 2 -> 1 -> 4 loop).

Your article addresses 1, but I don't think it says much about 2. Sure, sequences should probably trend downward over time, but why shouldn't a sequence that hops upward at the beginning get snagged on a value it's already hit as it falls back down, trapping it a nontrivial loop?

See Denend's thesis, around pg. 44

https://repositories.lib.utexas.edu/bitstream/handle/2152/74...

Eventually getting to a power of 2 means that n*3 must eventually, at some point, be a non-prime Mersenne number. If there were something about the initial conditions it feels like you'd be saying something about the distribution of Mersenne primes, which is unlikely?

Yes in pseudo C-like binary-oriented notation the step is:

if ( lowest bit of x is 0 ) x >>= 1 else x += ( x << 1 ) + 1

And it's immediately obvious that the else branch always produces an even number.

I am also wondering about that. I guess it is just one way to prove termination, it might be the case that this approach does not work for the Collatz conjecture.

Forgot that there's an xkcd, too:

https://xkcd.com/710/

The collate conjecture gets a pass from me because I think there’s an even more funded problem that is even more useless: calculating pi to more and more digits. I doubt any practical application needs more than 10 digits.

For fun I went ahead and wrote a little javascript to calculate the sequence. I realized that a lot of work would end up repeated as soon as you encountered an earlier number again (it's directed-graph traversal, really), so it records the ones that it's solved and bails out when it finds them again (denoted by the ->). You can paste the following into your browser console to get a feel for what it looks like.

    let memo = {}

    function conjecture(n) {
        let str = "";

        while (n !== 1) {
            str += n + " ";

            if (memo[n] != null) {
                str += "->";
                return str;
            } else {
                if (n % 2 === 0) n = memo[n] = n / 2;
                else n = memo[n] = n * 3 + 1;
            }
        }

        str += n + " ";

        return str;
    }
    function rangeTo(end) {
        return new Array(end).fill(null).map((_, i) => i + 1)
    }

    for (const n of rangeTo(1000)) {
        console.log(conjecture(n))
    }

A neat thing is that this terminates (at 1) for seemingly every number you try (I disabled console-logs and the process terminated for every number up to a range of 10,000,000, which is as high as I tested). It's just the formal proof that missing. There also seems to be a vague pattern to the results, but that may just be cloud-pictures.

Now that Fermat's Last Theorem has been proven, the Collatz conjecture is the simplest unsolved math problem. That is what makes it special. There are other unsolved problems that are at the heart of some rich field of mathematics and would be more mathematically significant to solve, like the Riemann hypothesis.

Yup, for the past two days, for the first time I thought about the problem!

Yup, quickly it gets to the role of prime numbers or a product of primes and some number of factors of 2.

Heck, obviously can draw a directed graph with an arc from each odd number, that is, a product of primes except 2, and the result of the 3X + 1 operation. Then have an arc from each even number to that number with one less factor of 2.

Then if could argue that given a number n, the nodes in the graph that can be reached from n are finite and if we don't enter cycles without a 1, then we are done!

Alas, as one might expect from all the effort on this problem, a gap here is the argument of finiteness, and that quickly gets to how many primes there are or are not! And as we know, where all the primes are is a tough problem.

Long ago in math, I decided not to spend effort on big questions about prime numbers!

So, I gave up, decided to use easier problems to think about when going to sleep!

To clarify my question above, there seems to be a general rule for calculating the next step in any Collatz-like iterated sequence from one odd number to the next, given the parameters (c, D) where both c and D are positive odd numbers and c > D, using the coefficients of each step's odd number, expanded in base-c. That is to say, 3N + 1 becomes cN + D.

The expansion's number of coefficients increases by 1 at each step until the leading coefficient becomes 0, and then continues. Although, it must be noted that the leading coefficient acts as a "pilot value" of sorts seeing that it is greater than c for most of the steps, given that each of the rest of the coefficients, call them s, are typical in that 0 ≤ s < c.

This reasoning is faulty since the same conjecture if you replace 3n+1 with 5n+1 turns out to be false. Interestingly the problem with a general pair of constants is undecidable.

> since 1 is added to a number, the number will eventually reach a power of 2

Why do you think that's the case?