Collatz Tree

For some reason, I have a fascination with all the different sequences of numbers that arise out of thinking about the Collatz conjecture. In this post, we’ll look at a few more of these.

The Collatz chain for a number N is the sequence of numbers that arise from repeatedly iterating the function
Screen Shot 2019-06-16 at 11.09.39 PM
until you get to 1. The Collatz conjecture is the statement that this sequence always terminates, no matter what n you start at.

In other words, f(N) is the function that tells you what N becomes after a single iteration. Let’s look at the inverse of this: what numbers become N after a single iteration?

One such number is 2N: 2N is always even, so after one step it falls down to n. Another possibility is m = (N-1)/3. Why? Well, if m is an odd number, then it will become 3m+1 = 3 (N-1)/3 + 1 = N – 1 + 1 = N. So for each N, we get either one or two new values.

The Collatz tree is what we get if we start at 1 and repeatedly iterate the inverse function. After n iterations, we get to the set of all numbers that take at most n steps to get to 1. Here’s what it looks like!

Screen Shot 2019-06-17 at 6.18.05 PM

I’ve never actually seen it plotted this way, and I think it shows something potentially important. Look at the order in the image! Why do we get this grid of apparently identical rhombuses? I’d love an explanation for this.

I also like the idea of “surfing” the jagged lower end of this graph, staying as small as possible while iterating f. In general, the lower end of the graph is the sequence of smallest numbers that take N steps to get to 1.

Here are the first thirty numbers in this sequence:

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 72, 25, 49, 98, 33, 65, 130, 43

Plotted, this sequence looks like:

Collatz Minimums

The first twelve of these numbers themselves form a Collatz chain. We leave this particular chain on the thirteenth step, at which point we enter a new chain containing 17. We stay in this new chain until seven steps later, at which point we enter a new chain containing 25. But now we only stay in this new chain for one step before departing for a new one! This is another sequence of numbers that fascinate me: the chain lengths at which our minimum values switch to entirely new chains. Here are the values for up to 100 steps:

12, 23, 24, 26, 27, 34, 36, 37, 38, 39, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 60, 61, 63, 64, 65, 72, 73, 74, 75, 76, 97, 98

The differences between these values are plotted here:

Differences

Whenever this plot spikes, this points to an existence of a Collatz chain that surfs the bottom of the Collatz tree for some time before jumping up to a higher value!