Friday, January 25, 2008

The 3n+1 conjecture (Collatz's conjecture)

The 3n+1 conjecture (Collatz's conjecture), forwarded from Open Problem Garden.

Let f(n) = 3n+1 if n is odd and n/2 if n is even. Let f(1) = 1. Assume we start with some number n and repeatedly take the f of the current number. Prove that no matter what the initial number is we eventually reach 1.

It can be also obtained from Wikipedia. This problem is worth at least $500 US dollars. Refer to this page for some results of computational verification. I also wrote a very simple program to verify this conjecture.

This is an an open problem for the moment, and it seems to be given on an graduate school entrance exam. To find a function g (n) such that f(n) = O(g(n)) is then an open problem, too.

It's very interesting. By the way, I found "Jones' conjecture", posted by Chuan-Min Lee. I hope that someday I will post an interesting and important open problem or a conjecture, too.

No comments: