What is the Collatz Conjecture?

Mathematical conjectures are riddles that challenge the human mind: seemingly simple problems that, despite having been verified in millions of cases, still lack a proof. They are seemingly intuitive questions that hide unexpected complexity. 

The fascinating thing about conjectures is that, in many cases, they can be empirically verified i.e., verified by an enormous number of numerical examples. However, this verification does not satisfy mathematicians, who seek a theoretical proof, a solid proof that validates the statement in its entirety. Without such a proof, the conjectures remain open challenges. 

The Collatz conjecture is a perfect example of this type of mathematical mystery. It was proposed in 1937 by Lothar Collatz and its statement is as follows: 

Choosing any positive integer we will apply the following steps: 

➔ If the number is even, we will divide it by 2. 

➔ If the number is odd, multiply it by 3 and then add 1. 

➔ Repeat the process with the new number obtained. 

The conjecture says that, no matter what number you start with, you will always get to number 1. Once you get to 1, the process repeats indefinitely: 1 →4 →2 →1

Formally, this can be written as the function f=N →N defined as

Two illustrative examples of the Collatz Conjecture

Let’s look at a couple of simple examples.

Let’s take the number n=6 and apply the steps of the Collatz conjecture:

1. 6 is even so we divide by 2: 6/2=3
2. 3 is odd so we multiply by 3 and add 1: 3·3+1=10
3. 10 is even so we divide by 2: 10/2=5
4. 5 is odd so we multiply by 3 and add 1: 3·5+1=16
5. 16 is even so we divide by 2: 16/2=8
6. 8 is even so we divide by 2: 8/2=4
7. 4 is even so we divide by 2: 4/2=2
8. 2 is even so we divide by 2: 2/2=1

Once we reach 1, the process is repeated: 1 →4 →2 →1.

So we observe that starting with n=6 the conjecture is satisfied.

Let us now take the number n=21 and apply the steps of the Collatz conjecture:

1. 21 is odd so we multiply by 3 and add 1: 21·3+1=64
2. 64 is even so we divide by 2: 64/2=32
3. 32 is even so we divide by 2: 32/2=16
4. 16 is even so we divide by 2: 16/2=8
5. 8 is even so we divide by 2: 8/2=4
6. 4 is even so we divide by 2: 4/2=2
7. 2 is even so we divide by 2: 2/2=1

Again, we arrive at number 1.

Both examples have reached the number 1, but in a different number of steps. In fact, although 21 is a larger number, it reached 1 in fewer steps than 6. This conjecture has been tested for an incredible number of numbers, up to more than 2ˆ60 = 1.152.921.504.606.846.976 cases, without finding any counterexample. However, it still remains a mystery whether there is a number that does not satisfy the conjecture.

Graphical representations of the Collatz conjecture

The directed graph of orbits is a visual representation that facilitates the understanding of the behavior of numbers under the rules of the Collatz conjecture. In this graph, each number is represented as a node, and the connections between them show the steps followed by the conjecture process. When following the sequence of a number, the nodes are connected by arrows that indicate how the number is transformed at each step. Although even numbers are generally omitted from the representation for simplicity, the graph illustrates how the numbers “orbit” around certain cycles, such as 1 →4 →2 →1.

In the image above, we can see an example of the directed graph of orbits, where we have highlighted in black the numbers 3 and 21. The number 3 refers to the sequence of 6, since in this graph the even numbers are omitted to simplify the visualization.

We note that 21 quickly reaches 1, since it only passes through even numbers on its way, as we saw in the previous example. On the other hand, the number 6 first becomes 3, then pass through the number 5, which will finally take it to 1 after several passes through even numbers. 

It is also interesting to note that the number 9, although relatively small, follows a longer sequence: it goes through the numbers 7, 11, 17, 17, 13 and 5, and finally reaches 1, after a total of 19 steps. 

Below is a graph in which the X-axis shows the different initial integer values, while the Y-axis represents the number of iterations required for each number to reach the value 1.

In summary, the Collatz conjecture is an apparently simple problem that, to this day, still has no formal proof. Although it may seem a statement of little relevance or practical utility, this conjecture has applications in various fields, such as number theory, cryptography, algorithm analysis and artificial intelligence. In these fields, the study of complex sequences and their behavior under specific rules can offer valuable insights for solving larger problems and understanding mathematical patterns.

Have you been fascinated by the simplicity and mystery of the Collatz conjecture? Now it’s your turn: take the number 27 and start the sequence. How many steps will you need to get to 1?

If this challenge got you, don’t keep it to yourself! Share it with others who are curious about mathematical riddles and find out together who can solve the challenge the fastest.