The 3x+1 conjecture is a very famous open problem in mathematics also known as the Collatz conjecture. It is known to be the simplest open problem such that a child with elementary math knowledge can understand it. The problem is the following: starting with any positive integer x, if it is even, divide it by 2, otherwise if it is odd, multiply it by 3 and add 1. Repeat this process indefinitely. For example, starting with 5, it’s odd so we multiply by 3 and add 1 to get 16, it’s even and so we divide by 2 to get 8, 4, 2, and then 1. Since 1 is odd, we multiply by 3 and add 1 to get 4 which again is reduced to 1. Clearly, we are stuck in the infinite loop 1, 4, 2, and 1. The conjecture is that no matter which positive integer you start with, you will always eventually reach 1. The conjecture has been extended to nonpositive integers, real numbers, and to even complex numbers.
This problem was first proposed in 1937 and so it is more than 80 years old. This seemingly simple problem has frustrated many brilliant mathematicians over all of these years. You might try to solve it but be warned, it is extremely addictive.
The question is of course: is it worth the effort? In other words, what could possibly be the benefit of settling this conjecture? Well, let me show you first what’s so fascinating about it.
Let f(x) be a function that represents the transformation mentioned above, which has been called “Half Or Triple Plus One”, or HOTPO. That is, let f(x) be the HOTPO of x. Define the Collatz sequence of x as follows:
x, f(x), f(f(x)), …
For example, the Collatz sequence of 5 is:
5, 16, 8, 4, 2, 1, 4, 2, 1, 4, …
The Collatz conjecture is that this sequence will eventually reach the number one regardless of which positive integer is chosen initially.
Let x be a positive integer. The total stopping time (TST) of x is the number of applications of the function f to reach 1. For example, the TST of 5 is 5, the TST of 2 is 1, and the TST of 1 is 0. Obviously the TST of any positive integer x is either nonnegative or infinity. The Collatz conjecture can be defined in terms of the TST of x as follows: the TST of any positive integer x is finite.
The TST can be used as an evidence to whether the conjecture is true or false. The following figure shows a histogram of the TSTs of the integers from 1 to 100 million where the x-axis represents the stopping time and the y-axis represents the frequency. We observe that the largest stopping time does not exceed 500, which seems surprising. Also the most frequent TST is around 175. This provides a strong evidence that the Collatz conjecture is true. In addition, since stopping times seem to be always small, we can write a program that can efficiently determine whether the Collatz sequence of a given integer reaches 1 or not. In fact, this method has been used to verify the conjecture for all positive integers up to 5 * 260.
Let’s go back to the question of why settling this conjecture is important in mathematics. Well there are two reasons. First, the Collatz sequence is very interesting by itself. The following figure plots the integers from 1 to 9999 against their corresponding total stopping times. Look at that graph! What’s up with the mysterious dash-followed-by-dot pattern? Also notice that the stopping times become more varying with larger starting positive integers. It would be nice to be able to explain this.
The second reason for why the Collatz conjecture is important is that it seems to have a connection with many other mathematical problems. In particular, it might shed some light on the relation between the prime factorization of an integer n and n+1. How?
Well, consider a particular positive integer n and consider what might happen to its prime factorization when the Collatz process (applying HOTPO indefinitely) is applied to it. What happens to the prime factorization of n when divided by 2? Not much. Since 2 is a prime number, the prime factorization of n will be almost the same. What happens if we multiply by 3? Also not much because 3 is a prime number. Now we will add 1 and this is where the prime factorization significantly changes. To see this, consider the number 20 whose prime factorization is 2*2*5. By adding 1 we get 21 whose prime factorization is 3*7 which is completely different from the prime factorization of 20! In other words, adding 1 to an integer has the effect of mysteriously shuffling its prime factors.
What the Collatz conjecture is saying is that given any positive integer, by repeatedly removing all twos from its prime factorization, adding the prime factor 3, then mysteriously shuffling its prime factors, we will eventually eliminate all prime factors and reach 1. Proving the Collatz conjecture might provide some insight on what’s happening to the prime factors possibly leading to new techniques to factorize integers.
Peter Schorer has recently published a document containing several proofs of the conjecture that are yet to be verified. They seem to be promising. It will be reviewed by mathematicians to determine their correctness. You can obtain the document from here.