So close, and yet so far…

I was given this riddle because of my interest in numbers. At first glance, it seemed simple. Little did I know, despite its tantalizing simplicity; how maddeningly addictive, or indeed how maddeningly complex this is. Only later did I look up and discover that some of the finest mathematicians, for years, have been trying to solve it. Some have even declared it probably unprovable.

 
I have no hope of solving it. That doesn’t stop me from playing with it.

So, here it is. Start with any random positive integer. If it is an even number, divide it by 2; if it is an odd number, multiply it by 3 and add 1 – and then repeat the process. For example, starting from 7, next number is 22 (7*3 + 1), next is 11 (22/2), next 34 (11*3 + 1) and on and on. The (in)famous Collatz conjecture predicts that you will always end up with the recurring 4 – 2 – 1 sequence; NO matter which integer you start from. Don’t bother checking this; people with more time to waste than you have verified this, using computers, for up to 21 digit-long numbers. But the Math purists, or even I, don’t consider that a ‘proof’.

 
The question is, can we prove mathematically that the series HAS TO end up in 4 – 2 – 1; or produce a counter-example, i.e. an integer whose series does not end up in 4 – 2 – 1? Interestingly, the only way to prove the counter-example is to show its series ends up in some other recursive loop!
So far, I am approaching this like a mystery; thinking of different techniques to attack, and made some simple discoveries (aka scratched the surface) on my own…

a. At any point in the series, if you hit some power of 2 (e.g. 16, 512, 1024… etc.), you are guaranteed to end up with 4 – 2 – 1, in a finite set of steps. How does this help? Now we 'just' need to prove that every series WILL eventually hit a power of 2.

b. By definition, every even number is either a power of 2; or is a power of 2 multiplied by an odd number. This allows us to focus only on the odd numbers in a series.

c. Every alternate power of 2 equals 3n + 1, where n is some odd integer – this can be proven almost trivially. Examples are 4 (=3*1 + 1), 16 (=3*5 + 1), but not 8, nor 32 etc. It helps a little bit to know that half the powers of 2 fit exactly the pattern of 3n + 1. Sadly, it doesn’t guarantee that 3n + 1 will be a power of 2 at any point. In theory, the series can go on infinitely without ever hitting a power of 2.

d. In the series, if we ever reach a number smaller than the original integer; we WILL reach the 4 – 2 – 1 loop in a finite number of steps. Obviously, we can see a stronger but harder to prove guarantee too! The only catch is to prove that we WILL reach a number smaller than the original number, at some point.

So frustrating to ‘know in your heart’ the conjecture is true, and yet not be able to prove it. Gödel's “Incompleteness Theorem” basically states that there are always some ‘truths’ that can not be proven within the system. This may well be one of those.