Collatz Conjecture or 3n + 1 Conjecture or Ulam Conjecture, is the problem in mathematics for almost a decade. It is proposed in 1937 by Lothar Collatz. Although extensively tested and always found true, this conjecture remains unproven, making it a persistent and enticing mystery in the world of mathematics.

Famous mathematicians Paul Erdős said about the Collatz Conjecture, “Mathematics may not be ready for such problems,” highlighting its deceptive simplicity and deep complexity. In this article, we will discuss this conjecture which seems true but still not proven by scholars.

What is Collatz Conjecture?

Collatz Conjecture, also known as the 3n + 1 conjecture, the Ulam conjecture, or the Syracuse problem, is a famous unsolved problem in mathematics. It was first proposed by Lothar Collatz in 1937.

The conjecture can be described using the following simple algorithm applied to any positive integer:

• If the number is even, divide it by 2.
• If the number is odd, triple it and add 1.

Repeat this process with the resulting number. The conjecture states that no matter which positive integer you start with, you will eventually reach the number 1 with end loop of 4-2-1.

Notation of Collatz Conjecture

For any positive integer n, define the sequence as follows:

[Tex]\bold{F(n) = \begin{cases} n/2, & \text{if n is even i.e., n\%2 = 0} \\ 3n+1, & \text{if n is odd i.e., n\%2 = 1}\end{cases}}[/Tex]

Other Names for Collatz Conjecture

The Collatz Conjecture is known by several different names, reflecting its wide recognition and the interest it has generated among mathematicians around the world. Here are some of the most common names for this conjecture:

• 3n + 1 Conjecture – Refers to the rule of multiplying by 3 and adding 1 when the number is odd.
• Ulam Conjecture – Named after Stanisław Ulam, a prominent mathematician who popularized interest in this problem.
• Syracuse Problem – Sometimes called this due to related work by mathematicians at Syracuse University.
• Hasse’s Algorithm – Named after Helmut Hasse, a German mathematician who studied this conjecture.
• Kakutani’s Problem – Named after Shizuo Kakutani, another mathematician who contributed to its study.
• Thwaites Conjecture – Named after Bryan Thwaites, who also studied and promoted this problem.
• Total Stopping Time Problem – Refers to the number of steps needed to reach the cycle of 4, 2, 1.

Checking Collatz Conjecture

Here’s an example of the iteration process starting with the number 6:

f(6) = 6/2 = 3

f(3) = 9 + 1 = 10

f(10) = 10/2 = 5

f(5) = 3 × 5 + 1 = 16

f(16) = 16/2 = 8

f(8) = 8/2 = 4

f(4) = 4/2 = 2

f(2) = 2/2 = 1

The sequence generated by the iterative application of the Collatz function is often represented as a directed graph, with each number in the sequence represented by a node, and edges connecting nodes to their Collatz function outputs.

The sequence generated by the example above can be represented by the following graph:

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Note: Collatz conjecture has been verified for all numbers up to 2.95×10²⁰.

Examples of Collatz Conjecture

We can take any starting number and put the value in the condition until we get 1 at the end with end loop of 4-2-1.

Here we will see two more examples one with n = 5 and other is n = 7. Let’s discuss about these.

Starting with n = 5

If n is odd, we apply the function f(n)=3n+1. So, f(5) = 3(5)+1 = 16.

If n is even, we apply the function f(n) = n/2 . So, f(16) = 16/2 = 8

f(8) = 8/2 = 4

f(4) = 4/2 = 2

f(2) = 2/2 = 1

5 → 16 → 8 → 4 → 2 → 1

The sequence reaches 1 after 5 steps, confirming the Collatz conjecture for n = 5.

Starting with n = 7

If n is odd, we apply the function f(n)=3n+1. So, f(7) = 3(7)+1 = 22.

If n is even, we apply the function f(n)= n/2 So, f(22) = 22/2 = 11.

f(11) = 3(11) + 1 = 34

f(34) = 34 /2 = 17

f(17) = 3(17) + 1 = 52

f(52) = 52/2 = 26

f(26) = 26/2 = 13

f(13) = 3(13) + 1 = 40

f(40) = 40/2 = 20

f(20) = 20/2 = 10

f(10) = 10/2 = 5

f(5) = 3(5) + 1 = 16

f(16) = 16/2 = 8

f(8) = 8/2 = 4

f(4) = 4/2 = 2

f(2) = 2/2 = 1

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

The sequence reaches 1 after 16 steps, confirming the Collatz conjecture for n = 7.

Fun Facts about the Collatz Conjecture

Some fun facts about the Collatz conjecture are:

• The conjecture is also referred to as the “hailstone sequence” or the “3n+1 problem.”
• It is one of the simplest mathematical problems to state but has evaded proof for over eight decades.
• Mathematicians have verified the conjecture for enormous starting values but have not proven its validity for all numbers.
• The Collatz conjecture is listed in the Guinness Book of World Records as the “simplest impossible math problem.”
• The Collatz conjecture is easy to understand but notoriously difficult to prove.
• There are numerous variations and extensions of the Collatz conjecture, including multi-dimensional versions and modifications to the rules.

Conclusion

Collatz conjecture is like a tricky puzzle in the world of math that has puzzled mathematicians for many years. It’s a simple idea but a tough nut to crack, challenging our understanding of numbers and calculations. While we’ve made progress in explorіng how it works for lots of numbers, provіng it true for all numbers still seems out of reach. Mathematicians are still trying to figure it out, and it remіnds us that there’s always more to learn in the fascinating world of math.

Read More,

• Modular Arithmetic
• Prime Numbers
• Odd Numbers
• Even Numbers

FAQs: Collatz Conjecture

How Did the Collatz Conjecture Get Its Name?

The conjecture is named after the German mathematician Lothar Collatz, who first proposed it in 1937. Collatz became interested in the problem while working on related questions in number theory.

Is there a prize for proving the Collatz conjecture?

No formal prize exists for proving the Collatz conjecture. However, the conjecture’s resolution would undoubtedly earn recognition and aclaim in the mathematical community.

What are some notable attempts to prove the Collatz conjecture?

Several mathematicians have proposed approaches and techniques to tackle the Collatz conjecture, including Paul Erdős, Terence Tao, and Jeffrey Lagarias, among others.

Has anyone discovered a counter example to the Collatz conjecture?

Despite extensive computational searches, no counterexamples to the Collatz conjecture have been found, further reinforcing its status as an unsolved problem in mathematics.

Are there any practical applications of the Collatz conjecture?

While the Collatz conjecture itself has no direct practical applications, the techniques and insights gained from studying it contribute to the broader field of number theory and computational mathematics.

Why is the Collatz conjecture considered so challenging to prove?

The Collatz conjecture’s simplicity masks its underlying complexity, as it exhibits intricate and unpredictable behavior that defies conventional proof techniques. Additionally, its universality makes it difficult to establish a general case, contributing to its elusive nature.