Understanding the Collatz conjecture





June 5 2024
Author: Wilson Chen
Edited by Kevin Guo



The Collatz conjecture, also known as the 3n + 1 problem, is a fascinating and deceptively simple problem in mathematics that has puzzled mathematicians for decades.





Understanding the Collatz Conjecture The Collatz conjecture, also known as the 3n + 1 problem, is a fascinating and deceptively simple problem in mathematics that has puzzled mathematicians for decades. It is named after Lothar Collatz, who first proposed it in 1937. Despite its straightforward rules, no one has been able to prove or disprove the conjecture for all positive integers. The Conjecture Explained The Collatz conjecture starts with any positive integer “n”. Then, you apply the following rules repeatedly: If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. The conjecture states that no matter what positive integer you start with, you will always eventually reach the number 1.


Examples
Let's look at a couple of examples to see how it works:


Starting with 6:

  • 6 is even, so divide by 2: 6/2=3
  • 3 is odd, so multiply by 3 and add 1: 3 * 3 + 1 = 10
  • 10 is even, so divide by 2: 10 / 2 = 5
  • 5 is odd, so multiply by 3 and add 1: 5 * 3 + 1 = 16
  • 16 is even, so divide by 2: 16 / 2 = 8
  • 8 is even, so divide by 2: 8 / 2 = 4
  • 4 is even, so divide by 2: 4 / 2 = 2
  • 2 is even, so divide by 2: 2 / 2 = 1

We have reached 1.



Starting with 11:


11 is odd, so multiply by 3 and add 1: 11 * 3 + 1 = 34

34 is even, so divide by 2: 34 / 2 = 17 17 is odd, so multiply by 3 and add 1: 17 * 3 + 1 = 52

52 is even, so divide by 2: 52 / 2 = 26

26 is even, so divide by 2: 26 / 2 = 13

13 is odd, so multiply by 3 and add 1: 13 * 3 + 1 = 40

40 is even, so divide by 2: 40 / 2 = 20

20 is even, so divide by 2: 20 / 2 = 10

10 is even, so divide by 2: 10 / 2 = 5

5 is odd, so multiply by 3 and add 1: 5 * 3 + 1 = 16

16 is even, so divide by 2: 16 / 2 = 8

8 is even, so divide by 2: 8 / 2 = 4

4 is even, so divide by 2: 4 / 2 = 2

2 is even, so divide by 2: 2 / 2 = 1


Again, we reach 1.


Why is it So Hard to Prove?

Despite the simple rules, proving that every positive integer will eventually reach 1 involves deep and complex mathematics. The difficulty lies in the fact that numbers can behave unpredictably when you apply the Collatz rules. Some sequences grow large before eventually shrinking to 1, and there's no clear pattern that applies to all numbers.


Mathematical Insights and Partial Proofs

Here are a few insights into why the conjecture is believed to be true, even though it hasn't been proven:

Computational Evidence: Computers have tested the conjecture for very large numbers (up to around 2^68) and found that they all eventually reach 1. While this isn't a proof, it provides strong evidence that the conjecture might be true.

Reduction: For many numbers, if you can show that a smaller number eventually reaches 1, you can use that to argue the larger number will also eventually reach 1. However, this approach hasn't yet covered all possible numbers.

Mathematical Properties: Some mathematical properties of the Collatz function have been studied extensively. For instance, the function has been shown to have a sort of "almost periodic" behavior for large classes of numbers, suggesting some underlying regularity.


Conclusion

The Collatz conjecture remains one of the great unsolved problems in mathematics. It is a beautiful example of how a simple question can lead to deep and complex mathematical investigation. Whether it is eventually proven true or false, the work done on the conjecture has already advanced our understanding of number theory in significant ways. Next time you encounter an odd number, try running it through the Collatz sequence and see how quickly you reach 1. You might just stumble upon something that even the world's greatest mathematicians have yet to discover!



Sources:

Bischoff, Manon. “The Simplest Math Problem Could Be Unsolvable.” Scientific American, https://www.scientificamerican.com/article/the-simplest-math-problem-could-be-unsolvable/. Accessed 5 June 2024.

Honner, Patrick. “The Simple Math Problem We Still Can’t Solve.” Quanta Magazine, 22 Sept. 2020, https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/. Accessed 5 June 2024.