Collatz Conjecture: Cutting the work in half

Hello all, there has been many things going on the last few weeks and I somehow neglected my little baby here. So today I want to investigate the Collatz Conjecture a little bit further. As a quick reminder, we are looking at a sequence of natural numbers with an arbitrary starting point:

And since I've been diving into python programming the last few weeks, why not make use of that and write a little function to speed things up?

def collatz(i):
    result=[i]
    while (i!=1):
        if (i%2==0):
            i = i /2
        else:
            i = i*3+1
        result.append(int(i))
    return(result)

So far we assume that the conjecture is correct. That is why the while loop is looking for i to reach 1 to terminate its run. Should this assumption lead to the while loop getting stuck because we started with a number that does not terminate, then we have hit the jackpot and I would be more than ok with terminating it the old fashioned way by hitting Ctrl+C. 😁

If we let that run and print the results for the first, let's say 17 numbers, then we get the following output:

[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[10, 5, 16, 8, 4, 2, 1]
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[16, 8, 4, 2, 1]

No surprises there, we find all the sequences terminating in [4, 2, 1] (with the obvious exceptions at the beginning). But what can we take from it? Are there any other patterns we might make use of?

Well, yes. Whenever we hit a number in our sequence, that is less than our starting number, we get an already known sequence. Have a look at these examples:

[3, 10, 5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[10, 5, 16, 8, 4, 2, 1]
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

We can apply the thinking of Proof by Induction at this point:

Assuming we test every number starting with 1 and going up to infinity. Whenever we start the sequence with a number N, all numbers before have already been tested and found to be ending in [4, 2, 1]. So if our sequence starting in N at any point leads to a number below N then we can be sure we already did run that particular sub-sequence at some prior point. With this in mind we can shorten the search for a starting number that does not end in [4, 2, 1] significantly.

def collatz_short(start):
    result = [start]
    i = start
    while (i>=start):
        if (i%2==0):
            i = i /2
        else:
            i = i*3+1
        result.append(int(i))
    return(result)

Careful not to put 1 as a starting number now. For all others we get the following result:

[2, 1]
[3, 10, 5, 16, 8, 4, 2]
[4, 2]
[5, 16, 8, 4]
[6, 3]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5]
[8, 4]
[9, 28, 14, 7]
[10, 5]
[11, 34, 17, 52, 26, 13, 40, 20, 10]
[12, 6]
[13, 40, 20, 10]
[14, 7]
[15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10]
[16, 8]

That output is a lot shorter. And less work for the computer. Additionally we notice something else: Every even number goes into the break condition immediately. Of course, it is an even number and therefore the next step is cutting it in half. Which in turn means we instantly arrive at a number we already checked.

And that leads to the first observation:

If there is a starting number N for which the Collatz Conjecture does not hold, then N must be odd!

So our main program can skip every even number and does not even have to start the function with it. Because we know it would just cut that number in half and then do an instant return with [N, N/2].

Not only have we shortened the run time of our function, we just eliminated half the natural numbers from our "suspect pool" of starting numbers.

That will be it for today. Next time we will look for another improvement, maybe there are other conditions to immediately tell if a starting number will definitely end in [4, 2, 1]?

Hidden Spoiler Text

Yes, there is. If you want to take a stab at it, feel free to do so in the comments.

---

_{Header image picture taken by me.
Math pictures created with latex.codecogs.com
If I made a blunder somewhere along the line and didn't catch it despite proofreading several times, please let me know in the comments so I can fix it.}