Calculate Collatz (3n + 1) sequence in C++

problem

You wish to print the infamous Collatz sequence also known as 3n + 1. Given a natural number greater than 0, if it’s odd you multiply by 3 and add 1, otherwise you divide it by 2 and repeat this process until it becomes 1. Fun fact about it is that it always ends with the number 1.

SOLUTION

Let’s write some code in C++ to print the sequence. Given a number n, e.g. 3 it will print 3, 10, 5, 16, 8, 4, 2, 1. Let’s start with a function that accepts an integer N and returns its next number given the Collatz logic.

 

The function prototype is as follows:

				
					int collatz(int n);
				
			

We assume that the input n is always positive number (greater than 0).

 

The implementation of the function:

				
					int collatz(int n) {
    if (n % 2 == 1) {
        return 3 * n + 1;
    } else {
        return n / 2;
    }
}
				
			

Now to call this function we will need to use a loop as follow:

				
					int res = 5;
    
while(res != 1) {
    cout << res << endl;
    res = collatz(res);
}

cout << res << endl;
				
			

The code above iterates until the result is 1. This way we can print the sequence. In the example above it should be:

Sequence output starting from 5
5
16
8
4
2
1
running

To make it more interesting, we can ask the user to input a number to calculate. So all together will look as follows:

				
					#include <iostream>
using namespace std;

int collatz(int n);

int main() {
    
    int res;

    cout << "Collatz numbers \n";
    cout << "Enter a number > 0: ";
    cin >> res;
    
    while(res != 1) {
        cout << res << endl;
        res = collatz(res);
    }
    
    cout << res << endl;

    return 0;
}

int collatz(int n) {
    if (n % 2 == 1) {
        return 3 * n + 1;
    } else {
        return n / 2;
    }
}
				
			
output

A simple example with the input 6. If the user enters a negative number, since there is no validation the program will enter an infinite loop.

conclusion

In this post we saw a simple implementation of the Collatz sequence in the C++ programming language.

Share it!

Facebook
Twitter
LinkedIn
Reddit
Picture of Ellion

Ellion

Professional IT consultant, writer, programmer enthusiast interested in all sorts of coding.
Eats all cookies 🍪

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x