Here’s something I’ve been puzzling about ever since I first heard of it a few weeks ago. It involves a very simple algorithm to apply to a natural number n. Let’s call it COLLATZ:

function COLLATZ(n):
if n is even: return n/2
else: return 3n + 1

The Collatz conjecture states that, for any natural number n > 1, repeated applications of the COLLATZ procedure will eventually yield 1.

We can see that the conjecture holds for small numbers:

n = 2
COLLATZ(2) = 1

To simplify matters, we will use an arrow (->) to indicate application of the COLLATZ procedure, so that the above expression could be rewritten as:

2 -> 1

Additionally, expressions that have been seen previously are omitted with an ellipsis (…). To resume demonstrating the convergence (or “oneness”) of some small numbers:

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
4 -> 2 -> 1
5 -> … -> 2 -> 1
6 -> 3 -> … -> 2 -> 1
7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> … -> 2 -> 1
8 -> 4 -> 2 -> 1
9 -> 28 -> 14 -> 7 -> … -> 2 -> 1
10 -> 5 -> … -> 2 -> 1
42 -> 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

I wrote a quick Python script to count the number of iterations required for any arbitrary n, and also to calculate the average number of iterations required over a range of numbers. Looking at the output of this script, along with reasoning about the conjecture itself, led me to the following conclusion:

The Collatz conjecture is true if and only if repeated application of the COLLATZ procedure always yields a power of two.

I will save the formal proof for later, but it shouldn’t be too difficult to see that the above statement is true. What is more difficult (and what has proven impossible for me so far) is proving that the COLLATZ procedure, if applied enough times, will always produce a power of two.

For odd n, it is apparent that COLLATZ(n) will be even, because three is odd, and an odd number multiplied by another odd number is yet another odd number, and one more than an odd number is an even number. An even number is a good start, because a power of two is necessarily even, but it’s quite a leap to say that we will always arrive at a power of two, no matter what number we started with initially.

Despite this difficulty, my tests seem to indicate that the conjecture does, in fact, hold, at least for the first several hundred thousand numbers on the number line. I plan to continue researching this phenomenon because it is quite fascinating to me.