DO the math, DON'T overpay. We make high quality, low-cost math resources a reality.

Thursday, September 25, 2014

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  a_0 , then apply the following recursion:

 a_n={1/2a_(n-1)   for a_(n-1) even; 3a_(n-1)+1   for a_(n-1) odd
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×1018

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."

No comments:

Post a Comment