Collatz conjecture proved?
Collatz conjecture proved?
Written by Mike James   
Saturday, 04 June 2011

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:

Collatz Conjecture

 

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

 

Banner


IPython 5.0-LTS Released
11/07/2016

IPython 5 is the first version to get Long term Support (hence the LTS name). It features a major upgrade to the terminal interface with new editing facilities which are provided by a cross-platf [ ... ]



Firecode - Ace the Coding Interview
27/06/2016

Another code learning platform, in this case focused on preparing candidates for a job interview that involves writing code. What's different about it? Let's find out.


More News

Last Updated ( Sunday, 25 January 2015 )
 
 

   
Banner
RSS feed of news items only
I Programmer News
Copyright © 2016 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.