100, 10, 1

Before we dive into the “solution” (or lack thereof), let’s take a look at the binary representation of a number. Imagine we have a number $n$n with a binary representation of:

$n=...b_4{b}_3{b}_2{b}_1{b}_0$n=...b4​b3​b2​b1​b0​

This gives rise to a value of:

$n=...+\left(2^4{b}_4\right)+\left(2^3{b}_3\right)+\left(2^2{b}_2\right)+\left(2^1{b}_1\right)+\left(2^0{b}_0\right)$n=...+(24b4​)+(23b3​)+(22b2​)+(21b1​)+(20b0​)

Notice how that apart from the $b_0$b0​ term, everything else is a multiple of 2? This means that n is even if and only if $b_0$b0​ is 0, and odd if and only if $b_1$b1​ is 1. Let’s call this Lemma 1.

Let’s define a number $n^{\prime }$n′ such that its binary representation is given as:

$n^{\prime }=...b_4{b}_3{b}_2{b}_1{b}_{0}0$n′=...b4​b3​b2​b1​b0​0

Where $b_k$bk​ are the digits from our original $n$n. Then $n^{\prime }$n′ would be:

In short, adding 0 to end of a binary representation of a number will double it. Let’s call this Lemma 2.

By the same logic, if a number’s binary sequence ends with a 0 (meaning it is an even number), then removing the 0 from the end will divide the number by 2. Let’s call this Lemma 3.

Let’s take a look at the rules of Cole’s program again:

• If the binary sequence ends with a 0, delete it.
• Otherwise, add a 0 to the end, add the original sequence to it, then add 1 to it.

Taking what we have just learnt, we know that the machine takes in a number $n$n, then outputs:

• $\frac{n}{2}$2n​ if $n$n is even (by Lemma 1 and Lemma 3).
• $2n+n+1$2n+n+1 if $n$n is odd (by Lemma 1 and Lemma 2).

Simplifying the second rule, we get:

• If a number is even, divide it by 2.
• If a number is odd, multiply it by 3, then add 1.

We’ve arrived at the Collatz Conjecture.

Consider the function f:

Then the Collatz Conjecture states that regardless of which integer $n$n you begin at, applying the function $f$f repeatedly to it will eventually result in reaching the number $1$1.

Applying $f$f repeatedly to $1$1 will result in the sequence $1\to 4\to 2\to 1$1→4→2→1 repeating, which is the 100, 10, 1 sequence we’ve seen in our earlier examples. Cole’s hypothesis and the Collatz Conjecture are equivalent.

However, the Collatz Conjecture, at this time of writing, has not yet been solved. If either Cole’s hypothesis or the Collatz Conjecture is proven or disproven, then the other one is automatically proven or disproven too. Until then, we’ve got some ways to go.