In 1937, Lothar Collatz, a German mathematician, posed the famous Collatz conjecture, which remains unsolved today. Paul Erdős has offered $500 for its solution.
What is the Collatz Conjecture?
Take any positive number n:
- If n is even, divide it by two;
- If n is odd, triple it and add one.
In modular arithmetic notation, the function f is defined as:
Next, we form a sequence by repeating this over and over again, taking each result as the input for the next step.
The Collatz Conjecture states that:
“This process will eventually reach the number 1, regardless of which positive integer is chosen initially.”
The conjecture suggests that, regardless of the starting number, the sequence will always reach the number 1, and form a 4 – 2 – 1 loop which will repeat infinitely.
The total stopping time of n is defined as the smallest i such that ai (the ith number of the sequence) is equal to one. If for some n, such an i doesn’t exist, then the conjecture is false – n has an infinite stopping time. However, no such n has been found.Reverse Collatz
An alternative form of the conjecture is that 1 leads to all natural numbers using the reverse relation. However, we must remove the 1 – 2 – 4 loop (the inverse to the 4 – 2 – 1 loop). To avoid this, mathematicians substitute the relation 3n+1 of function f, by a ‘shortcut’ relation (3n+1)/2. Hence, the ‘Collatz Graph’, which is created as a result, is defined as follows:
This conjecture has been checked for all starting values up to 260 . However, this brute-force method will only be sufficient as proof if the conjecture is false and a counterexample is found, as we cannot check an infinite amount of numbers in finite time.
Importance of this Conjecture
The Collatz conjecture is one of the simplest open problems in mathematics; you can explain to all your non-mathematical friends or even small children and they will understand it. Despite its simplicity, it relates to not only number theory, but also to topics such as:
- Chaos: in cellular automata;
- Decidability: John Conway showed that similar questions are formally undecidable;
- The foundations of mathematics and computation: Emil Post’s tag systems.
When I read about this conjecture I was fascinated by its simplicity, and it reminded me of Fermat’s Last Theorem in the sense that it is easy to understand but overwhelmingly difficult to prove.
What are your favourite undecided problems in mathematics? M x