Simple is not always easy

Last week I wrote about a simple process that can generate complex patterns. Today's topic is the equally 'simple' but unproven Collatz conjecture. This is how it works:

• Choose any positive integer.
• If the number is even, divide it by 2.
• If the number is odd, multiply it by 3 and add 1.
• Repeat steps 2 and 3.

The Collatz conjecture states that this process will eventually reach the number 1, no matter what number you start with.

The image at the top of the page shows what happens when we choose 36 as a starting number. The number of steps to reach 1 varies depending on where we start. If you continue after reaching 1, the sequence will loop infinitely as follows.

Counting steps

A few lines of Python (or your language of choice) easily enables us to count how many steps it takes to reach 1 from a given starting number.

def ProcessNumber(startNum):
    # Even numbers get halved, odd numbers 
    # are multipled by 3 and 1 is added.

    count = 0

    while True:
        if startNum == 1:
            return count

        if startNum % 2 == 0:
            startNum /= 2
            count += 1
        else:
            startNum = startNum * 3 + 1
            startNum /= 2
            count += 2
        

A little more Python provides some interesting insights. The first table below shows the starting numbers between 2 and 1 million that take the most steps to reach 1. The second table shows the highest values that were attained before finally decreasing to 1 again.

Final thoughts

A proof for the Collatz conjecture has eluded mathematicians since 1930. The last time I checked, the highest number tested was somewhere around 2 to the power 68 or something like a 3 with 20 zeros after it if you prefer decimal. Without a formal proof, there may always be a higher number that disproves the conjecture.

Sometimes the simplest looking problems can be the most difficult to solve.