1
$\begingroup$

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

Linear Relationship for Class (2, 1), Dropping Time = 1

Class (4, 3) Graph

Linear Relationship for Class (4, 3), Dropping Time = 3

Class (16, 9) Graph

Linear Relationship for Class (4, 3), Dropping Time = 6

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.

Linear Relationship for Class (32, 27), Dropping Time = 8

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

Linear Relationship for Class (32, 27), Dropping Time = 8

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)

Linear Relationship for Class (128, 81), Dropping Time = 11

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:

Pythagorean Tuning Intervals - From D

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!

$\endgroup$
5
  • 6
    $\begingroup$ It's certainly interesting, though I have no clue whether or not it's novel. A couple of points. (1) You should learn to use MathJax/LaTeX formatting. Ideally all of the variables and equations should be typeset this way. It's a long post so I'm not going to edit it. (2) The connection with music theory, while not trivial, is simply equivalent to the fact that you're using $2^n$ and $3^m$. Because an octave is a $2:1$ ratio, and a perfect fifth is a $3:2$ ratio, working with lots of twos and three creates some parallels with music theory. $\endgroup$ Jun 13, 2022 at 23:28
  • 1
    $\begingroup$ The sequence oeis.org/A122437 which is $i+\lceil i \log_2(3)\rceil$ is well know for the first value $k$ smaller than $n$ especially when $k=n$ (study of cycles), but still to be proved. The sequence oeis.org/A100982 of possible combinations of paths (for fixed $i,m$ with $t=i+m$) is well known in Collatz Sieves (when discarding sequences with $k<=n$, see en.wikipedia.org/wiki/Collatz_conjecture#Modular_restrictions). It is also well known that starting number $n$ and $n+2^m$ have the same path (at least on length $t$) and will lead to $k$ and $k+3^i$ $\endgroup$
    – Collag3n
    Jun 14, 2022 at 10:24
  • 1
    $\begingroup$ Also the study of the continued fraction of $log_2(3)$ is closely linked to Collatz cycles, but also to musical scales as Eric mentioned $\endgroup$
    – Collag3n
    Jun 14, 2022 at 10:32
  • 1
    $\begingroup$ To be more precise: ($n_0+r\cdot 2^m$,$k_0+r\cdot 3^i$) will give you a linear plot (for fixed $i,m$) $\endgroup$
    – Collag3n
    Jun 14, 2022 at 10:46
  • 2
    $\begingroup$ To adresss the main question : No, the collatz conjecture cannot be solved with patterns. It turned out to be just too dynamical. This conjecture has been checked upto a depth that cannot be imagined, so if there would be some pattern allowing an "easy" proof, the probhability is very high that it would be solved. $\endgroup$
    – Peter
    Jun 15, 2022 at 9:50

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The number of surviving residues $\mod(2^{\lceil i log_23\rceil})$ is $s_i=s_{i−1}\cdot 2^{\lceil i log_23 \rceil−\lceil(i−1)log_23⌉\rceil} - a(i)$ with $s_1=1$ and where $a(i)$ is the ith term of this sequence oeis.org/A100982 (see discussion on this sieve: math.stackexchange.com/questions/3454674/…). This is almost oeis.org/A076227, except some values in this sequence are just doubled when there is a jump in the sequence (due to the use of the ceiling function) $\endgroup$
    – Collag3n
    Jun 27, 2022 at 8:45
  • $\begingroup$ more precisely, $s_i$ is the $\lceil i log_23\rceil ^{th}$ element of the sequence oeis.org/A076227 (with "surviving residues" = "uncertain classes"). And when there is "0 drops", the value is just the preceding value doubled. $\endgroup$
    – Collag3n
    Jun 27, 2022 at 11:31
  • $\begingroup$ I apologize for having to comment on this post for correspondence, but I'm looking to reach Dr. Jacobs. I've had some exciting new developments come out of these ideas, and I'd like to share, and perhaps collaborate on finishing them. I searched for an email online but could not find one. Dr. Jacobs, if you'd be willing, could you send me an email at dthomas.is at outlook.com. I'm looking forward to sharing some results related to your answer here. $\endgroup$
    – dthomas
    Sep 22, 2023 at 18:19
  • $\begingroup$ @dthomas, I received your message via another platform. Thank you for reaching out $\endgroup$ Sep 23, 2023 at 17:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .