Understanding Collatz Sequence in Python

Hello coders!! In this article, we will be learning about the collatz sequence in Python. We will first understand what it means. Then we will follow it by understanding the implementation of the collatz sequence in Python. So, let us get straight into the topic.

What is the collatz sequence?

Suppose there is a positive integer n. Then the next term of the collatz sequence will be as follows:

  • If the previous term is even, the next term is half of the previous term, i.e., n/2
  • If the previous term is odd, the next term is 3 times the previous term plus 1, i.e., 3n+1
  • The conjecture is that no matter what value of n, the sequence will always reach 1

Illustration of collatz sequence:

Let us consider the first number of the sequence to be 3.

2nd Term:

  • The previous term is 3, which is odd.
  • So, the next term will be (3*3 + 1) 10.

3rd Term:

  • The previous term is 10, which is even
  • So, the next term will be (10/2) 5.

4th Term:

  • The previous term is 5, which is odd.
  • So, the next term will be (3*5 + 1) 16.

5th Term:

  • The previous term is 16, which is even
  • So, the next term will be (16/2) 8.

6th Term:

  • The previous term is 8, which is even
  • So, the next term will be (8/2) 4.

7th Term:

  • The previous term is 4, which is even
  • So, the next term will be (4/2) 2.

8th Term:

  • The previous term is 2, which is even
  • So, the next term will be (2/2) 1.

As we have reached the value 1, the sequence is now complete.

 3, 10, 5, 16, 8, 4, 2, 1

Collatz conjecture function in python:

def Collatz(n): 

	while n != 1: 
		print(n, end = ', ') 

		if n & 1: 
			n = 3 * n + 1

		else: 
			n = n // 2
	print(n) 

Collatz(21) 

Output:

21, 64, 32, 16, 8, 4, 2, 1

This is a straightforward code that we have used to implement Python’s collatz sequence. We have defined a function Collatz() that takes in an integer variable as input. Then we have used a while loop to print the sequence. We first check the nth term. If it is even, we change it to n/2. Else, we change it to 3n+1 and print that term. We continue this process till the number becomes 1, giving the desired output.

 Collatz conjecture Python recursion:

def collatz(n):
    list1 = [n]
    if n == 1 :
        return [1]                 
    elif n % 2 == 0 :
        
        list1.extend(collatz(n//2))     
    else:
        list1.extend(collatz(n*3+1))    
    return list1

collatz(21)

Output:

[21, 64, 32, 16, 8, 4, 2, 1]

In this code, we have used recursion to obtain the collatz sequence. We check the parameter that is passed to the collatz() function. If it is 1, i.e., the last term of the sequence, then recursion is stopped, and 1 is returned in the list. Otherwise, if the element is even, the collatz() function is recursively called with the value n/2, and the result is extended to the list. However, if the element is odd, the collatz() function is recursively called with the value 3*n+1, and the result is extended to the list. In the end, the list is returned, giving the desired result.

Longest collatz sequence python:

import time
start = time.time()
# to cache the values
cache = {n: 0 for n in range(1,1000000)}
# initial values
cache[1] = 1
cache[2] = 2
# looping through the numbers
for n in range(3,1000000):
    counter = 0
    current = n
    while n > 1:
        if n < current:
            cache[current] = cache[n] + counter
            break
        if n%2 == 0:
            n = n/2
            counter += 1
        else:
            n = 3*n+1
            counter += 1
print(list(cache.values()).index(max(cache.values()))+1)
print(time.time()-start)
837799
4.36925745010376

In this code, we have used a dictionary to store the pre-calculated values of the collatz sequence. We reduce the time complexity of the program from O(n^2) to O(nlogn). As we have to find the largest sequence between 1 and 1 million, we’ll use the cache to save our time for recalculation. This technique is termed Memoization.

Memoization is the process of storing the results that have already been computed. In this code, we have used the memoization technique in order to optimize our code. We have created a dictionary ‘cache’. Then we iterate the loop to 1 million to find the number that will generate the longest collatz sequence. We store all unique numbers in the dictionary ‘cache’ and finally display the number with the maximum collatz sequence. The time taken by this code to execute is 4.36925745010376 due to optimization using memoization.

Below is the same code done without memoization:

import time
start = time.time()
def collatzSeq(n):
    chainNumber = 1
    current = n
    while current != 1:
        if current % 2 == 0:
            current = current/2
            chainNumber += 1
        else:
            current = (3*current) + 1
            chainNumber += 1
    return [chainNumber, n]
data = []
for i in range(2, 1000000):
    data.append(collatzSeq(i))
print(sorted(data, reverse=True)[:1][0][1])
print('Time:', time.time() - start)
837799 
Time: 27.117942571640015

When the above code is executed, you will notice that it takes around 30 seconds more than the one with the memoization code. So, you can clearly see the difference between the time taken by the two codes.

Collatz Python sequence Infinite loop bug:

def collatz(n):
    if n % 2 == 0:
        n = n // 2
        print(n)
        return n
    elif n % 2 == 1:
        n = n * 3 + 1
        print(n)
        return n

print('Enter an Integer')
n = int(input())
while n > 1:
    collatz(n)

When we run the above code, we see that we get stuck in an infinite loop. This happens because return only holds the new value if you assign it to a variable. To correct this error, we need to format the code as follows:

while n > 1:
    n = collatz(n)

Collatz conjecture number of steps:

We can modify our program of collatz sequence to get the number of steps involved in getting the collatz sequence of a number.

def collatz(n):
    if n == 0:
        return 0
    cnt = 1
    while n != 1:
        n = (n / 2) if n % 2 == 0 else (3 * n + 1)
        cnt += 1
    return cnt

print(collatz(3))
8

As you can see, we have just modified the above code and used a counter variable ‘cnt’ to calculate the number of steps required to get the collatz conjecture.

Must Read

Conclusion:

With this, we come to an end with this article. In this article, we learned about the collatz sequence. We also learned how to implement the collatz sequence in Python both recursively and non-recursively.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

Subscribe
Notify of
guest
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Andy
Andy
1 year ago

This was very very helpful. Thank you, I was breaking my mind with an infinite loop