A proof has been proposed for the Collatz conjecture by a German mathematician who is a former student of Collatz who originally came up with this addictive problem. If it is solved it may improve the lives of mathematicians everywhere.

If you don't know what the Collatz conjecture is then you haven't missed out on anything really important - with the possible exception of the excellent Xkcd cartoon reproduced below:

The cartoon is accurate but let's make the conjecture clear:

• Pick a number, a positive integer.
• If even divide by 2
• If odd multiply by 3 and add one
• Repeat above two steps with new value

If you try it you will discover that you eventually reach a result of 1. For example, 10, 5,16, 8, 4, 2, 1. At first you think it must be an accident and so you try a few more tests. Then you become obsessed and write a program - and you always end up at 1.

So far it has been verified for values up to 5.76x10^18.

The Collatz conjecture is that this is indeed always true but can you prove it?

The sequence of numbers is also known as a "hailstone sequence" and the conjecture is a "halting problem". It is has already been proved that for a generalization of the sequence the problem is undecidable - but this doesn't settle the specific conjecture.

Somehow it seems like a simple problem but it is remarkably tough and it just goes to prove that very complex systems arise out of simple algorithms. Only in this case it is the proof of the behavior that is complex, not the actual behaviour. It is an example of a class of iteration problems that are hard to prove.

Paul Erdos (and if you don't know who he is you're not even interested in mathematics) said of the conjecture:

"Mathematics is not yet ready for such problems"

and he offered $500 for a solution.

The problem also has a reputation for being addictive if you have that sort of mind. It was reported then when introduced to Yale everyone worked on it but got no where. The same thing happened when the problem arrived at the University of Chicago and it quickly got a reputation for being a conspiracy to slow down mathematical research in the US.

Now at long last a German mathematician, Gerhard Opfer, a former student of Collatz has announced a proof. It hasn't been peer reviewed yet but you can read the pre-print.

So is the problem solved?

The paper runs to 32 pages and we will have to wait for it to be checked for errors. Such is mathematics in the Internet age - no longer are proofs brought down from the mountain top in their perfection but they are thrown to the crowd to survive being torn apart.

UPDATE: After flaws were found in this proof, seeThe Collatz conjecture is safe (for now), it was withdrawn and the conjecture remains open.

See:

 An analytic approach to the Collatz 3n + 1 Problem

Related reading:

Computability