An Old Problem in Disguise

Here is a well known mathematical problem stated in a slightly different way than usual. See if you can find out which problem I am talking about.

Start with any binary number ending in a 1, e.g.

100101101

Now shift this number one place to the left, filling the rightmost digit with a 1

1001011011

then add this number to the original number

100101101
   1001011011
   ----------
   1110001000

Finally eliminate all trailing zeros

1110001

Now repeat the whole process until you reach the number 1. The question is, will you always end up at the number 1, irrespective of the number you started with?

You probably guessed it by now that this is the well known Collatz problem. In its standard form the Collatz conjecture reads

Given a starting number x₀ and the recursion






the sequence x_n will always reach the number 1.

I have always been fascinated by this problem, but never so seriously that I would have started reading up on it and following the newest results. Only recently I started pondering over it and came up with the representation in the beginning. Naive that I was, I thought I could see some patterns in the binary representation of the problem. Of course I was in no way the first person to think of this an some further reading on Wikipedia revealed that this is one of the standard alternative representations of the problem. Some more extended Google search revealed this online script for calculating the Collatz number sequence in binary form.

I like the binary representation because it somehow reminds me of cellular automata. In a cellular automaton the state of a cell in the next generation is determined by the states of the cells in a given neighbourhood in the previous generation. Although it looks similar, the binary Collatz problem doesn't map in a straightforward way onto a cellular automaton. This is because the addition of the two binary numbers can cause non-local changes due to the carry over. It turns out, however, that there is a way of translating the Collatz problem into a cellular automaton.

There are a few patterns that one can identify in the binary representation. If a number x ends on k ones then there will be k successive steps where the 3n+1 operation just adds one zero at the end. This means that the number will grow from its original value x to


On the other hand, if x ends in k alternating ones and zeros, then the next 3n+1 operation will turn this sequence into zeros and the result will be


These quick investigations have certainly sparked my interest in the Collatz conjecture again, and I am now looking forward to reading a bit more in depth on the problem.