The Collatz Conjecture

The Collatz conjecture is a famous mathematical mystery that has yet to be solved. It is named after Lothar Collatz a German mathematician, who first proposed it in 1937.

It is based on the following number sequence:

• Start with any positive whole number called n,
• if n is even, divide it by 2: n’ = n / 2,
• if n is odd, multiply it by 3 and add 1: n’ = 3 x n + 1,
• if n’ = 1 then stop the number sequence,
• otherwise repeat this process with n’ as your starting number.

Let’s see how this number sequence behaves with some of the following numbers:

These number sequences are known as hailstone sequences because they go up and down just like a hailstone in a cloud before crashing to Earth.

It seems that these sequences always end up reaching an endless cycle: The endless cycle being 4, 2 , 1. (If we carry on, 1 being odd becomes 3 x 1 + 1 = 4).

An unsolved problem:

The question that these sequences are raising is: Does such number sequences always settle on the 4,2,1 cycle no matter what starting value we use? It is conjectured (but not yet proven) that they will, in other words that each hailstone sequence will always terminate at n = 1.

Experiments certainly suggest that it does. Computers have checked all starting values up to 5 x 2⁶⁰, a number that is 19 digits long, and found that the 4, 2, 1 cycle eventually appears. The trouble is that nobody has been able to prove that this is the case for all starting numbers!

This unsolved mathematical question/unproven conjecture is known as the Collatz conjecture.

Your Challenge

Write a computer program that will implement a hailstone number sequence. Ask the user to input the starting number and display all the numbers generated by the number sequence till you reach the value of 1. Make sure that your number sequence follow the rules listed at the beginning of this blog post.

Extension Task:

Did you use iteration (for instance a while loop) to complete this challenge?

If so do some research about how recursion works. Change your code to swap your loop for a recursive approach.