Collatz Conjecture Remains Unproven Despite its Easy Arithmetic


Home / Collatz Conjecture Remains Unproven Despite its Easy Arithmetic

The Collatz Conjecture

Come to think of it, starting with either “2” or “4” gives exactly the same sequence, only with a different starting point.

So let’s start with “3”. We find {3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1…}. The “same old, same old” final repeating sequence finishes this off. Obviously, starting with “5” would just be a shortcut into this sequence.

Collatz conjectured that starting with any positive integer would eventually end with this repeating sequence. That is to say, he believed it to be true but could not prove it with mathematical rigor.

The article “Lothar Collatz”, dated 2006, states that this had been verified for numbers up to about 10^14 (100,000,000,000,000). Of course, this evidence does not count as proof; we simply have not yet found a counter-example.

More recently, “The easiest math conjecture it took 74 years to prove” told of an proof that was later “withdrawn”. The problem was on page 11 of 32, according to the author’s note on the pre-print PDF.

Observations about the Collatz Conjecture’s Series

Let’s think about the function “f(n)” with its two rules. What can we notice about it?

My first thought is, “An odd number increases more than 1.5 times faster than an even number decreases”. That’s because of the factors “3” and “2” in “3*n” versus “n/2″.

But then, every time we have an odd number, the next number is even. That’s because of the “+ 1″ in “3*n + 1″. So the “3*n” increase can only happen once before the “n/2″ rule decreases the value.

How frequently is the “n/2″ rule repeated before we can make the number bigger with “3*n + 1″? Every even integer, “e”, can be written as “e=m*2″. Half of all integers are even; the others are odd. So, if the Collatz conjecture’s sequence just happens to be random, half the time we would use the “n/2″ rule once because that even number factors into 2 and an odd number. But the other half of the time, it factored into 4 (or a higher power of 2) and an integer. So we might expect “on average” to mulitply a number in the Collatz series by 3/4…or less.

Starting with “6” just brings us back to “3”. In fact, starting with any even number “e” gives the same final sequence as starting with “e/2″.

Finally, if the series lands on a power of 2, then the series collapses directly to 1. If n=2^m, then dividing by 2 means that the next number in the Collatz series is 2^(m-1), down to 2^0=1.

Collatz Graph Image by TerrorBite

Leave a Comment