Regarding math problems, theories, or conjectures, some are not proven on a large scale and some are as mysterious and unsolved as they were when introduced. Mathematicians and researchers worldwide are working continuously to prove these theorems and we occasionally hear them succeed.
The Collatz conjecture, also called the 3x + 1 problem or hailstone sequence, takes a starting number. If it’s even it gets divided by 2. If it’s odd, it gets multiplied by 3 and 1 gets added. This repeats until reaching 1. It is an unsolved conjecture about all numbers reaching 1, named after Lothar Collatz who introduced it in 1937.
In this post, we are going to talk about one such mathematical problem – The Collatz sequence. To explain this problem for starters, it takes a natural number and if that number is even, divides it into half. If the number is odd, it multiplies the number by three and adds one to the result. Hence, it is also called a 3x+1 problem. And when this process occurs iteratively over the result, we are supposed to end up with the number 1.
Learn how to plot mathematical functions here
What is the Collatz Conjecture?
The Collatz sequence goes by two other names – The hailstone sequence and the 3x+1 conjecture, introduced by Lothar Collatz in 1937. It checks if a natural number can be transformed into the number 1, by following two operations.
The operations included in the Collatz conjecture are as follows.
- If the number n is even, it is divided into half(n/2)
- If the number is odd, the number is multiplied by 3 and added to 1(Hence the name 3x+1 conjecture)
Let us take an example. Suppose the number is 8(even).
Iteration 1: Since n is even, we perform division
8/2=4
Iteration 2: n is even again, so divide by 2
4/2=1
Iteration 3: Divide by 2 since the result is even again
2/2 = 1
Collatz sequence for number 8 is 8 4 2 1
Let us take another example. Assume n=5(odd).
Iteration 1: Since n is odd, multiply by 3 and add 1
5*3+1 = 16
Iteration 2: The result is an even number, divide it by 2.
16/2=8
Iteration 3: Even number, divide by 2
8/2=4
Iteration 4: From here on, it is same as the Collatz sequence of 8.
Collatz sequence of 5 is 5 16 8 4 2 1
And just like that, we can compute the Collatz sequence of any number.
Why Is It Called the Hailstone Sequence?
The Collatz sequence is also called the hailstone sequence based on its resemblance with the hailstones in the sky. Just like how hailstones bounce up and down before falling to the ground, the numbers in the Collatz sequence also increase and decrease before reaching the value 1.
Recommended Read: Assert Keyword in Python
Implementing the Collatz Sequence in Python
Let us write a simple Python program to compute the collatz sequence.
def collatz(n):
seq = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
seq.append(n)
return seq
In the above code snippet, we have defined a function named collatz that takes a number n, and creates a list called seq which initially has the number itself. Then, we apply the condition – if the number is not equal to 1, and if it is even the number is divided by 2. Else, it is multiplied by three and added to 1. The result is appended to the seq list.
Next, we write the main function.
def main():
try:
number = int(input("Enter a positive integer: "))
if number <= 0:
print("Please enter a positive integer.")
return
seq= collatz(number)
print("Collatz sequence:", seq)
except ValueError:
print("Invalid input. Please enter a valid integer.")
if __name__ == "__main__":
main()
In the main function, we check if the number we input is natural and positive.
How to check if the numbers in a given range eventually settle at 1?
def collatz(n):
seq = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
seq.append(n)
return seq
def test_collatz_conjecture(start, end):
for i in range(start, end + 1):
seq = collatz(i)
print(f'The collatz sequence of {i} is {seq}')
test_collatz_conjecture(1, 15)
We have used the same code for checking if the number has a collatz sequence(the collatz function) and also used a different function called – test_collatz to check if the digits are in the range of 1 to 15.
The collatz sequence of 1 is [1]
The collatz sequence of 2 is [2, 1]
The collatz sequence of 3 is [3, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 4 is [4, 2, 1]
The collatz sequence of 5 is [5, 16, 8, 4, 2, 1]
The collatz sequence of 6 is [6, 3, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 7 is [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 8 is [8, 4, 2, 1]
The collatz sequence of 9 is [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 10 is [10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 11 is [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 12 is [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 13 is [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 14 is [14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
The collatz sequence of 15 is [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
In this way, we can verify if every number in the given range reaches 1 after applying the collatz sequence.
Summary
In this post, we have discussed the most popular unsolved math problem – The 3x+1 conjecture. We have discussed how to compute the collatz sequence theoretically and also implemented the collatz sequence using Python. In addition to this, we have also discussed the reason why the conjecture is also called the Hailstone Conjecture.
The Collatz conjecture remains an intriguing unsolved problem. Will we ever be able to prove all numbers reach 1? What insights could a proof provide into the nature of numbers? What do you think?