Can someone explain these groups of linear patterns in the dropping times of Collatz Sequences? Could this lead to a proof?

Question

Please buckle in because this may be a long post, but I think it will be necessary to help the reader understand three things:

• How this data was generated.
• How the data is grouped into different 'classes'
• How these classes relate to each other.

Collatz Dropping Times

The dropping time of n is the total number of Collatz iterations until a number is reached that is smaller than n. So, for example, every even number has a dropping time of 1, since we divide by 2 in the first iteration, which will result in a number lower than n. Finding the dropping time for even numbers are trivial. The simplest way to break this down is to look at n % 4.

• If n % 4 = 0, the dropping time is 1 (n is even)
• If n % 4 = 1, the dropping time is 3
• If n % 4 = 2, the dropping time is 1 (n is even)
• If n % 4 = 3, the dropping time is >= 6

One difficulty we've had so far is proving that every value of n where n % 4 = 3 has a finite dropping time. In other words, the Collatz Sequence does not diverge off to infinity. In this post we will take a look at different ways to classify numbers based on their dropping times, as well as some of the linearity within these classes.

Allowable Values for the Dropping Time of n

The dropping time for any given number cannot be arbitrary. A122437 on OEIS describes the sequence of allowable values. There are a couple formulas for generating these sequences, but we don't have a way to calculate the dropping time for a specific n without performing Collatz Iterations.

In the following section I propose what I'm calling 'Collatz Classes' which are groups of numbers that have the the same dropping time. Furthermore, I show some structure within, and between these classes. What I'm hoping to put forth is a way to make progress on the Collatz Conjecture by showing that every number >= 2 fits into one of these classes. I don't have the rigurous proof, but what I do have is a lot of compelling data!

Investigating Dropping Times

Take a look at the table below, which shows the dropping times for numbers 2-10. It's just a few values from this sequence: A102419

• n is the starting number
• k is the the next value in the Collatz iteration that is lower than n
• dropping time is the dropping time of n. i.e. the number of steps it took until k was reached.

\begin{array}{|c|c|c|} \hline n & k & \texttt{dropping time}\\ \hline 2 & 1 & 1\\ \hline 3 & 2 & 6\\ \hline 4 & 2 & 1\\ \hline 5 & 4 & 3\\ \hline 6 & 3 & 1\\ \hline 7 & 5 & 11\\ \hline 8 & 8 & 1\\ \hline 9 & 7 & 3\\ \hline 10 & 5 & 1\\ \hline \end{array}

There is no discernable pattern in this sequence, but in the previous section I pointed out that the only interesting dropping times are those that are >= 6. The reason I introduce this table is to introduce Collatz Classes. A Collatz Classes are described by two numbers (a, b):

• a is the distance from n to n_next, where n_next is the next number that is a part of the same class.

• b is the distance from k to k_next, where k_next is the next number that is a part of the same class.

These are the trivial properties of Collatz Classes. There are, however, a few more properties that I conjecture hold true, but have not yet proven.

• The dropping time of n and n_next are equivalent.
• a is always of the form 2^m
• b is always of the form 3^n
• The dropping time time for class (2^m, 3^n) is m + n
• For all classes where a > 2, let j = a - b. j is a part of this sequence. That is to say, j is the difference between between 3^i and the next larger power of 2.

To make this concrete, let's look at the trivial Collatz Classes.

Collatz Class (2, 1)

Every even number falls into this class. Here are the first 5.

\begin{array}{|c|c|c|c|c|c|} \hline n & k & \texttt{n_next} & \texttt{k_next} & \texttt{n_next - n} & \texttt{k_next - k} & \texttt{class}\\ \hline 2 & 1 & 4 & 2 & 2 & 1 & (2, 1) \\ \hline 4 & 2 & 6 & 4 & 2 & 1 & (2, 1) \\ \hline 6 & 3 & 8 & 6 & 2 & 1 & (2, 1) \\ \hline 8 & 4 & 10 & 8 & 2 & 1 & (2, 1) \\ \hline 10 & 5 & 12 & 10 & 2 & 1 & (2, 1) \\ \hline \end{array}

• a = 2

• b = 1

• m = 1 since 2^1 = 2 = a

• n = 0 since 3^0 = 1 = b

• the dropping time of this class is m + n = 1 + 0 = 1

Collatz Class (4, 3)

Every number n where n % 4 = 1 falls into this class. Here are the first 5.

\begin{array}{|c|c|c|c|c|c|} \hline n & k & \texttt{n_next} & \texttt{k_next} & \texttt{n_next - n} & \texttt{k_next - k} & \texttt{class}\\ \hline 5 & 4 & 9 & 7 & 4 & 3 & (4, 3) \\ \hline 9 & 7 & 13 & 10 & 4 & 3 & (4, 3) \\ \hline 13 & 10 & 17 & 13 & 4 & 3 & (4, 3) \\ \hline 17 & 13 & 21 & 16 & 4 & 3 & (4, 3) \\ \hline 21 & 16 & 25 & 19 & 4 & 3 & (4, 3) \\ \hline \end{array}

• a = 4
• b = 3
• m = 2 since 2^2 = 4 = a
• n = 1 since 3^1 = 3 = b
• the dropping time of this class is m + n = 2 + 1 = 3

Collatz Class (16, 9)

Every number n where n % 16 = 3 falls into this class. All numbers in this class are also solutions to the congruence n % 4 = 3. I still consider this a trivial class, since I've found no evidence of any further structure within this class (more on that when I discuss the non-trivial classes. All non trivial classes have more complex inner structure.

\begin{array}{|c|c|c|c|c|c|} \hline n & k & \texttt{n_next} & \texttt{k_next} & \texttt{n_next - n} & \texttt{k_next - k} & \texttt{class}\\ \hline 3 & 2 & 19 & 11 & 16 & 9 & (16 , 9) \\ \hline 19 & 11 & 35 & 20 & 16 & 9 & (16 , 9) \\ \hline 35 & 20 & 51 & 29 & 16 & 9 & (16 , 9) \\ \hline 51 & 29 & 67 & 38 & 16 & 9 & (16 , 9) \\ \hline 67 & 38 & 83 & 47 & 16 & 9 & (16 , 9) \\ \hline \end{array}

• a = 16
• b = 9
• m = 4 since 2^4 = 16 = a
• n = 2 since 3^2 = 9 = b
• the dropping time of this class is m + n = 4 + 2 = 6

A Note on the Trivial Classes

So we've discussed 3 classes so far - I consider these the trivial classes.

• (2, 1)
• (4, 3)
• (16, 9)

The reason I consider these classes trivial is because there are no subclasses within these classes. That is to say, the relationship between all elements that appear in the class can be described simply by (a, b). Further more, when you graph elements in these classes on a 2d plane where the n is on the X-Axis, and k is on the Y-Axis, you get a nice linear graph where the elements are spaced out evenly. Take a look at the following graphs below.

Class (2,1) Graph

Class (4, 3) Graph

Class (16, 9) Graph

Nontrivial Collatz Classes

The rest of the Collatz Classes that exist are nontrivial. I will list some of the classes below, and then investigate the first few in detail. My conjecture is that there an infinite number of Collatz Classes.

All Collatz Classes have an integer property I call a "mod-interval". I'm not sure if there is already a mathematical term for this idea, but it isn't too difficult to describe. All trivial class have a mod-interval value of 1. All nontrivial classes have a mod-interval value that is greater than one. Instead of trying to describe what a mod-interval is, I will list some Collatz Classes along with their mod-intervals, then we'll jump right into discussing Collatz Class (32, 27) which has a mod-interval of 2.

• (2, 1) mod-interval: 1
• (4, 3) mod-interval: 1
• (16, 9) mod-interval: 1
• (32, 27) mod-interval: 2
• (128, 81) mod-interval: 3
• (256, 243) mod-interval: 7
• (1024, 729) mod-interval: 12
• (4096, 2187) mod-interval: 30
• (8192, 6561) mod-interval: 85
• ...

Collatz Class (32, 27)

To start off, let's look at the graph of this class, just like we did with the trivial classes.

It's hard to spot by eye, but you can definitely see that though these numbers are linear in their relationship, they are not distributed evenly as a whole. They seemed to be grouped into sets of two, I call these sub-classes. This is why I classify these classes of having a mod-interval of 2 - there are 2 subclasses. Each element in this class satisfies at least one of the following conditions:

• n % 32 = 11
• n % 32 = 23

Now, if we redraw the graph and color and distinguish the elements by color, indicating which rule they obey within this class, you'll be able to see the relationship.

• Elements where n % 32 = 11 are RED
• Elements where n % 32 = 23 are GREEN

It's much easier to see how, within each subclasses, each element is nicely spaced out. Not only are the elements linear, but they're distributed evenly, just like the trivial classes! So in a way, the subclasses resemble the nontrivial classes.

Just for fun, I'll include one last bit of data for the (128, 81) Class.

Collatz Class (128, 81), mod-interval: 3

Subclasses:

• n % 128 = 7 (RED)
• n % 128 = 15 (GREEN)
• n % 128 = 59 (PURPLE)

Wrapping Up

I will wrap up this post since it has gone quite long, but I want to end it with what I feel is significant about this data.

• If we can somehow figure out how to find a way to detect which Collatz Class n falls in, we should be able to quickly deduce it's dropping time. Stated again, if n is in Collatz Class (2^m, 3^n), then it's dropping time is m + n. We still need to prove this.

• There may be a connection to music theory here. It may be somewhat of a stretch, but if you interpret the Collatz Classes as musical intervals, there is a very close relationship to Pythagorean Tuning. Below is a table from the wiki:

The frequencies circled in red correspond directly to the first set of Collatz Classes we observe (excluding class (2,1), which would be an "octave" in music theory). Perhaps there are methods from harmonic analysis that can be used investigate Collatz. Again, it may be a coincidence, but perhaps we could explore this relationship and see if there any new tools we can use on Collatz.

Subclasses

There is much more to be investigated with respect to the subclasses of nontrivial classes, namely, the distance between the first element of each subclass. I've found that this distance is always a multiple of 4. A quick example for Class (128, 81).

First Elements: [7, 15, 59]

15 - 7 = 8 = 4 * 2
59 - 15 = 44 = 4 * 11
128 - 59 = 76 = 4 * 19

Furthermore, if you take the distances computed [8, 44, 76] and do sort of a fibonaci operation and add them, you get numbers that show up in this sequence!

e.g. [8, 8 + 44, 8 + 44 + 76] = [8, 52, 128]

Sequences Related to this Post

• A122437 - Allowable dropping times for Collatz iterations. I conjecture that there is a unique class for all of these dropping times t, where class (2^m, 3^n) have dropping time t, and n + m = t

• A186008 - These numbers seem to be related exactly to the subclasses . You can use the distance between the first element of each subclass to compute every number in this sequence.

• A100982 - This sequence lists all of the possible values for mod-intervals for nontrivial Collatz Classes.

What else is there to say?

Full disclaimer, I am not a mathematician by trade, more of a hobbyist. I did my undergrad in computer science, and like to search for patterns in data. I also love to play the guitar, and found it really interesting that music intervals showed up in Collatz! If you have any comments on this approach or have a link to some related approaches, I'd be grateful if you left a comment! Or if there is a pretty clear explanation as to where this structure comes from, please leave me an answer! Thanks!

Answer 1

This is an interesting approach to the problem, which has been investigated to some extent, but you might have some novel insights. I'm going to translate some of this line of thought into more traditional mathematical language, and perhaps shed some light on where the Collatz classes come from.

We are looking at Collatz sequences modulo powers of 2. Let's start with 2, and then 4, then 8, etc.

Modulo 2

Every number is congruent to either 0 or 1. That means every number can be written in one of two forms:

$n_{2,0}=2j \\ n_{2,1}=2j+1$

Applying the Collatz function (let's denote it $\xrightarrow[C]{}$) to each, we see that $n_0$ drops immediately:

$2j \xrightarrow[C]{} j$, and $j$ is clearly less than $2j$. This is simply the observation that even numbers drop in one step.

The odd numbers, with form $n_1$, do not reveal anything to us, modulo 2:

$2j+1 \xrightarrow[C]{} 3(2j+1)+1 = 6j+4 \xrightarrow[C]{} 3j+2$

The result after 2 steps, $3j+2$, is not smaller than our starting value, and it could be even or odd, depending on the value of $j$, so we can't go any further. Rather, to go further, we need a larger power of 2.

Modulo 4

We've already dealt with the even numbers. Only the $2j+1$'s are a problem, and they split into two classes, modulo 4.

$n_{4,1}=4j+1 \\ n_{4,3}=4j+3$

Now we chase these through the Collatz function until we've done two divisions by 2:

$4j+1 \xrightarrow[C]{} 12j+4 \xrightarrow[C]{} 6j+2 \xrightarrow[C]{} 3j+1 \\ 4j+3 \xrightarrow[C]{} 12j+10 \xrightarrow[C]{} 6j+5 \xrightarrow[C]{} 18j+16 \xrightarrow[C]{} 9j+8$

As we can see, $n_{4,1}$ drops in 3 steps, but $n_{4,3}$ becomes uncertain after 4 steps, without dropping yet. Let's see if the next power of 2 tells us more:

Modulo 8

Our remaining class, $n_{4,3}$, splits into two classes modulo 8: $n_{8,3}$ and $n_{8,7}$. Observing these:

$8j+3 \xrightarrow[C]{} 24j+10 \xrightarrow[C]{} 12j+5 \xrightarrow[C]{} 36j+16 \xrightarrow[C]{} 18j+8 \xrightarrow[C]{} 9j+4 \\ 8j+7 \xrightarrow[C]{} 24j+22 \xrightarrow[C]{} 12j+11 \xrightarrow[C]{} 36j+34 \xrightarrow[C]{} 18j+17 \xrightarrow[C]{} 54j+52 \xrightarrow[C]{} 27j+26$

Neither of these dropped, as far as we can see modulo 8. That means we will have 4 classes, twice as many, to deal with next.

Modulo 16

Here we have $n_{16,3},n_{16,7},n_{16,11}$, and $n_{16,15}$. Sparing you the gory details, only one of the four drops here. We have $16j+3$ becoming $9j+2$ after six steps. The other three, have to push to mod 32, giving us six classes at that level.

Linear relation

What we have seen so far explains a few things in your observations. For example, numbers of the class $n_{16,3}$ drop when they have changed, in six steps, from $16j+3$ into $9j+2$. These are precisely the numbers that you identified as Class(16,9). At any rate, a linear (or affine linear) transformation turns $16j+3$ into $9j+2$, namely, $n\mapsto \frac{9}{16}n+\frac{5}{16}$. That is the line that appears in your graph.

Your non-trivial classes are the ones corresponding to larger powers of $2$, where more than one new drop appears. We haven't seen any of those yet in my analysis, so let's get a bird's eye view, and see them.

Overview

This analysis can be continued, and here are the overall results for the first few powers of 2. Note that the number of classes we start with for each power of 2 is simply the number of uncertain classes from the previous power, doubled:

$2$: 2 classes, 1 drops, 1 uncertain

$4$: 2 classes, 1 drops, 1 uncertain

$8$: 2 classes, 0 drops, 2 uncertain

$16$: 4 classes, 1 drops, 3 uncertain

$32$: 6 classes, 2 drops, 4 uncertain $\leftarrow$ This is your Class(32,27): 2 new drops $\implies$ 2 subclasses

$64$: 8 classes, 0 drops, 8 uncertain

$128$: 16 classes, 3 drops, 13 uncertain $\leftarrow$ This is your Class(128,81): 3 new drops $\implies$ 3 subclasses

$256$: 26 classes, 7 drops, 19 uncertain

$512$: 38 classes, 0 drops, 38 uncertain

$1024$: 76 classes, 12 drops, 64 uncertain

$2048$: 128 classes, 0 drops, 128 uncertain

$4096$: 256 classes, 30 drops, 226 uncertain

$8192$: 452 classes, 85 drops, 367 uncertain

$16384$: 734 classes, 0 drops, 734 uncertain

$32768$: 1468 classes, 172 drops, 1296 uncertain

Notes: The cases where there are no new drops are entirely predictable. Whenever two powers of $2$ occur between consecutive powers of $3$, the second one will have no new drops.

First, between $3$ and $9$, we have both $2^2=4$ and $2^3=8$. The latter: $8$, has no new drops. Then, between $27$ and $81$, we have both $32$ and $64$; the latter has no new drops. The only powers of $2$ that give us new drops are ones that "pass" a new power of $3$.

Additionally, the number of "uncertain" classes shown above are found in https://oeis.org/A076227

I hope that this perspective addresses your question. If I should say more, please let me know.