Collatz Conjecture

The Collatz Conjecture (or Syracuse Conjecture), also known as the 3n+1 problem, states that applying the 3n+1 algorithm to any positive integer will always end up with the number 1.

The conjecture remains unproven to this day: it is simple to state, but extremely difficult to prove.

Take a number number $ n $ (non-zero positive integer), if $ n $ is even, divide it by $ 2 $, else multiply by $ 3 $ and add $ 1 $. Start again by giving $ n $ the value of the result previously obtained.

Mathematically the algorithm is defined by the function $ f $: $$ f_{3n+1}(n) = \begin{cases}{ \frac{n}{2}} & {\text{if }}n \equiv 0 \mod{2} \\ 3n+1 & {\text{if }} n \equiv 1 \mod{2} \end{cases} $$

When the value $ 1 $ is obtained, continuation is generally considered complete, because the algorithm renders in an infinite loop of 4, 2, 1, 4, 2, 1, 4, 2, 1.

The sequence is generally considered to be finished at 1, because otherwise the following numbers are 4, 2, 1, 4, 2, 1, 4, 2, 1 which are repeated endlessly.

If the number $ n $ is odd, then multiplying it by $ 3 $ and adding $ 1 $ necessarily makes it even, the next step is necessarily a division by 2.

The compressed (or shortened) version merges the $ 3x+1 $ and $ x/2 $ calculations into a single step $ (3x+1)/2 $

To date, no positive integer contradicts the Syracuse conjecture.

This is why the conjecture is also called the Syracuse problem or the Collatz problem, and why it is not a theorem.

It has been verified by computers for billions of values, but no general mathematical proof exists.

Finding a single number that never reaches $ 1 $ would be enough to demonstrate that the conjecture is false.

The conjecture remains unproven, despite dozens of pseudoscientists claiming to have a proof.

In 2020, mathematician Terence Tao obtained a partial result: he showed that the conjecture is true for almost all integers, in the probabilistic sense. However, no complete proof yet exists.

A number never appears twice in the sequence. (This is also an open problem: prove that there are no loops/cycles)

Any sequence ends with a series of powers of 2.

An odd number is always followed by an even number.

The numbers 5 and 32 give the same result.

The conjecture can be written as a single expression as $$ \frac{(7n + 2) - (5n + 2)(-1)^n}{4} $$ if $ n $ is even, then $ (-1)^n = 1 $, and $ \frac{(7n + 2) - (5n + 2)}{4} = \frac{2n}{4} = \frac{n}{2} $ and if $ n $ is odd, then $ (−1)^n = −1 $ and $ \frac{(7n + 2) + (5n + 2)}{4} = \frac{12n + 4}{4} = 3n + 1 $

There are several ways to program source code for the 3x+1 algorithm:// Javascript
function step(n) {
if (n%2 == 0) return n/2;
return 3*n+1;
}
function collatz(n) {
var nb = 1;
while (n != 1) {
n = step(n);
nb++;
}
return nb;
}// Python
def collatz(n):
list = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
list.append(n)
return list

The Collatz conjecture/problem is also known as

— 3n+1 conjecture (or 3x+1)

— Hailstone conjecture

— Ulam conjecture

— Kakutani's problem

— Thwaites conjecture

— Hasse's algorithm

— Syracuse problem

— HOTPO (Half Or Triple Plus One)

The name Syracuse comes from the Syracuse University, a city in the state of New York in the United States, where this conjecture was raised in the 1950s.

This table is for numbers until 1000 (total time/iterations => numbers)

This table shows numbers until 1000 (max number reached => numbers)

The table above shows altitudes up to 250504 for numbers up to 1000. But there are infinite numbers that go higher.

For any given number N (very large N), then the odd number closest to N will have an even greater elevation.

The conjecture was formulated in 1937 by the German mathematician Lothar Collatz.