Monday, October 11, 2010

Unsolved Problem - The Collatz Conjecture

I was introduced to the Collatz Conjecture, also called the 3n+1 problem, in graduate school.  This is one of the many problems in mathematics that are easy to state, can be understood by middle school students, but is difficult to prove.

The set-up of the problem is simple.  Define the function below on the natural numbers.
The "phi" funcion

The problem is to prove that if you start with any natural number and repeatedly apply this function, you will eventually get back to 1.  For example:
  • 4 -> 2 -> 1
  • 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
This is a very easy algorithm to program into a computer or even a graphing calculator.  Computers have been used to test the first billion billion (10^18) or so natural numbers, and each returns to 1 eventually.  This would be enough for most people, but mathematicians need to know that there is not some unimaginably large number that will not go to 1.

Many people have tried to prove the Collatz Conjecture, and none have yet succeeded.  For me, the draw is that I can feel that there is a solution on the tip of my tongue.  It is the feeling that comes when you know there is a solution that you will see when you look at the problem in the correct way.  Despite that feeling, I have yet to find the solution.