Throwback Fact of the Week - Collatz Conjecture - 9/25/14

Collatz Conjecture

This conjecture is named after German mathematician, Lothar Collatz, who first proposed the problem in 1937. 

Start with any positive integer   , then apply the following recursion:

Credit: mathworld.wolfram.com

The Collatz conjecture states the following: regardless of which positive integer is chosen initially, this sequence of numbers will always eventually reach 1.

For example, starting with 10 (which is even, so divide by 2) you get the following sequence of numbers (5,16,8,4,2,1). Or starting with 7 you get (22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1). Note that upon reaching 1 you then get (4,2,1,4,2,1...) indefinitely.  

Despite the apparent simplicity with which the problem is stated, there has been no proof that every positive integer will eventually reach 1 using this recursion. While there has been no proof that it works for every integer, it has been checked to work for every number up to 5.764×10¹⁸

The Collatz Conjecture has fascinated mathematicians for decades. Mathematician Paul Erdos even commented on the complexity of the problem by saying "Mathematics is not yet ready for such problems."