The Collatz Conjecture is a deceptively simple mathematical conjecture devised by Lothar Collatz in which he proposed that you could take any positive integer and eventually reach one from it via performing one of two calculations. Either divide the number by 2 if it’s even otherwise multiply it by 3 and then add 1 and this will always lead to an endless loop of 1-4-2-1, or so the theory goes at least. As far as anyone can tell this conjecture seems to be completely true however to this day it remains unproven for certain and many mathematicians believe it is completely unprovable with the methods available today.
Libraries and Function Declarations
The only library that you’ll need for this program is “iostream” for the purposes of getting user input and displaying the program’s results as implementing the conjecture itself requires nothing more than basic arithmetic.
Next you’ll need to declare the function which will actually perform the Collatz Conjecture for the user. This should be a void function that takes a single unsigned double long variable for an argument. The reason for using this variable type over an int is just to ensure the user will be able to input very large numbers without the program breaking.
#include <iostream> void conjecture(unsigned long long n);
Main Function
Inside your main function you need to ask the user for the number they want to perform the Collatz Conjecture on, it should be an unsigned double long like the argument in the function we defined in the last section.
Once you’ve gotten the user’s input call the Collatz Conjecture function and pass the input into it.
int main()
{
unsigned long long userinput;
std::cout << "Enter a Number" << std::endl; std::cin >> userinput;
std::cout << '\n';
conjecture(userinput);
}
Next you should move on to defining your Collatz Conjecture function.
Collatz Function
Inside the function you should define an int variable that will hold the number of steps it takes the program to reach 1 from your starting number, set it equal to 0 for now. Once you’ve done this create a while loop that runs for as long as your “n” variable is not equal to 1.
void conjecture(unsigned long long n)
{
int steps=0;
while(n!=1)
{
Inside the while loop you’ll need to print out what step the program is currently on so that way the user can watch the full progression.
After that you’ll need to set up the two rules of the Collatz Conjecture. First check if “n” is divisible by 0 and if so divide it by 2. If its not divisible by 2 instead multiply n by 3 and then add 1 to it. Also be sure to increment the steps variable up by one before the loop repeats itself.
void conjecture(unsigned long long n)
std::cout << steps << ". " << n << std::endl;
if(n%2==0)
{
n=n*.5;
}
else if(n%2!=0)
{
n=(n*3)+1;
}
steps++;
Once the loop has finished simply print out a short message telling the user exactly how many steps it took to get the number to 1.
void conjecture(unsigned long long n)
std::cout << steps << ". " << n << std::endl;
if(n%2==0)
{
n=n*.5;
}
else if(n%2!=0)
{
n=(n*3)+1;
}
steps++;
Now this function should theoretically cause n to equal 1 eventually no matter what number it started out as.
Further Suggestions
If you want to take your Collatz Conjecture to the next level you should try creating a version of the program which displays its results as an actual branching tree starting from the first number as opposed to just a generic list like we have now.
Good Luck!
Download the above source code here.
If you have any questions or comments email them to me at nick@crumbsofcode.com
