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!
Ellion
Professional IT consultant, writer, programmer enthusiast interested in all sorts of coding.
Eats all cookies 🍪