Implementing 3x+1 or Collatz Conjecture In Python

Introduction

So, recently I was watching a on 3x+1 or Collatz Conjecture, this was my first exposure to this simple yet unsolved Maths problem. It has two simple rules to be followed indefinitely:

1. Take a number and check if it’s even or odd

2. If it’s even, divide it with two else multiply it with 3 and add 1 to the result

   
   

When performed with any number indefinitely, at some point the result is reduced to 1.

This is contradictory given we are just halving the number when it is even whereas adding 1 after tripling it if it’s found to be odd. The number should increase but instead, no matter how big or small a number is it gets reduced to 1.

What are we gonna do?

I am not a mathematician so, I won’t be claiming to solve any of this. Instead, let’s use some Python code to see what happens to a number when we apply the rules to it. We will also store all the numbers we come across in the process.

As this is a problem where we have to repeat a few given steps repeatedly and indefinitely we’ll be using a while loop and will stop our program once we reach 1 as once we reach 1 the program is supposed to be stuck on a loop of 1,4,2,1 ( as 1 multiplied with 3 and incremented by 1 gives 4 and dividing 4 gives 2 which is further reduced to 1). We don’t wanna be stuck in that never-ending loop we’ll pause execution once we reach 1.

Let’s proceed with the script

Firstly, we need a user input to have a number to progress with.

num = int(input(‘Enter a number: ‘)

Now, let’s initialize an array to store the numbers we come across during the process.

sequence = [num]

We’ll now enter our loop to apply the rules:

while(num != 1):    # this condition makes the loop stop once we reach 1
    if((num%2)==0):
        num = num//2    # re-assigning num with a new value
    else:
        num = (num*3) + 1    # re-assigning num with a new value
    
    sequence.append(num)    # appending number to the list

That’s it . Let’s just wrap our loop and the remaining code in a function so that it is reusable:

def collatz_conjecture(num):
   num = int(input('Enter a number: '))
   sequence = [num]
   while(nuum != 1):
       if((num%2)==0):
           num = num // 2 
       else:
           num = (num*3) + 1
       sequence.append(num)
   return sequence

Let’s try our function and see how the numbers are reduced to 1:

# sequence for 15
[15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

# sequence for 89
[59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 
44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

# sequence for 20000
[20000, 10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 704, 352, 
176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Conclusion

Implementing the rules wasn’t a tedious task it was fairly simple and has only one loop to cope with and just two conditions to check. You can build upon the results though, like plotting charts to measure the randomness but the mere implementation of this problem does not provide any programming challenge I did it for fun. And am posting the article so those who never came across this interesting problem get to know about it.

There have been warnings about this problem being dangerous as it can consume a lot of one’s work and still yield no results.Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."