Collatz conjecture

So the Collatz conjecture or 3n+1 problem is a pretty neat problem that is very simple to understand, but has very hard to crack mathematical properties. The problem is like prime numbers. Like prime numbers, I tinkered around with this problem and found some nice properties by reversing the problem as well as found a more generalized form of the problem. In hindsight, I have to say that the reversal was not really necessary, but made this easier to explain. I don't know if this has been done before as I only watched a Veritasium video on the subject, but here we go.

To reverse the problem we are basically going to look at if we can generate all positive integers with the inverse function defined in the Collatz conjecture. The inverse is however a bit different in how we are going to use it. Basically, the division by 2 can always be applied, while on the other hand the inverse of 3n+1 can only be used on certain numbers. The inverse of 3n+1 restrict further by only using it on even numbers, this will result in only getting odd numbers as those can not be generated by the inverse of division by 2. Lastly, our starting point will be 1, unlike the original problem where we start with any arbitrary number.

With this in place we can start to look at some of the properties of this inverse of the problem. First of all, we can create a set. We start with the number 1 as that is the start of our problem and then continuously multiply it by 2 and adding it to the set. Basically, this will contain all numbers of the form 1*2^n. The beauty in that it is a very simple form, would you do this with the 3n+1 you will get a polynomial of degree n. An important property of this set is that it only contains one odd number, which is the basis of our set.

With this set we can start trying to apply the inverse of 3n+1. First, we can skip the base number 1 of our set by definition. From there on we can find that the first solution we find for the number 4 which becomes 1, this is basically the loop of the 3n+1 problem. The subsequent solutions are found in a repeat interval, where between two solutions there will be exactly 1 number that does not have a solution for the inverse of 3n+1. The next solution we will find at 16 which becomes 5. 5 is a new number that we can use to generate a set in the same fashion as with 1. Unlike the set with basis 1, there will not be a loop. The first solution for the inverse will be at 10 which will become 3. Now 3 is an odd one and you might be able to spot it. When we create a set with the basis 3 like 1 and 5, there will not be any solutions to the inverse. This is obvious as any number in the set is a multiple of 3 and if you subtract 1 you cannot divide by 3 anymore.

The process described above basically finds what I call coverage sets, where each set has a base number. This means that the problem becomes about jumping between these sets, as every even number belongs to a set with an odd base number. These sets are all disjoint and the union of all coverage sets if we take all odd numbers as base numbers we get the set of all positive integers. I also like to note that these sets have a kind of fractal like structure together.

With the process and the coverage sets, we can extend the process such that we can create a series. Basically with we start the series with 1. To find the next value we take the union of all coverage sets with base numbers in the series and find all solutions of the inverse of 3n+1 as defined before and remove the solutions that are already in the series. We then take the minimum of that set and add it to our series. The series that follows is:

1, 5, 3, 13, 17, 11, 7, 9, 21, 29, 19, 25, 33, 37, 45, 49, 53, 35, ...

One of the properties of this series is that if you take any positive integer and apply the Collatz conjecture operations on it and only write down the odd results in reverse, you get a partial finite result of this series.

Now there is one more property I want to highlight and that is that the inverse of 3n+1 is bijective(logically as 3n+1 is linear and thus bijective). This means in our series, every odd number will only appear at most once. What we need to prove is that every odd number appears at least once in the series.

A simpler problem and a more generic one

Now, 3n+1 is pretty advanced if you ask me, let us try something more simple like n+1. The only thing that changes is the series we get which will be basically all odd numbers in order. This can simply be explained as that the search process will try and find the first number where there is a gap which will be the first odd number after the numbers we already found. Additionally, there will still be a loop, just a little bit smaller between the numbers 1 and 2.

This is also the start of our generalization. The function that can replace 3n+1 must have the same properties. These are that it must be bijective as well as transform an odd number to an even and vice versa. It can easily be seen that we can then replace 3 with any odd number. Furthermore, we can write the function as a*n+b, where a is odd and b can be any integer that is not divisible by a or the division number. The next step is to define what numbers we can replace with 2 in the division step. The answer is any positive integer. This will influence how we define the properties of 3n+1. Basically, this function is now defined as transforming a number that is a multiple of 2 to a number that is relatively prime to 2 and vice versa. If we take the general form, it changes the restriction of a to be relative prime to whatever the division number is chosen.

To wrap up. Personally, I think this problem has a lot in common with the regular problem of primes and that is what I like. The similarity is that it is a recursion of all information that is needed to produce the next number. However, unlike primes it seems, to me at least, a lot smaller and does not scale as fast as primes do. I also love the chaotic nature of the series, and I will probably write a calculator to generate these series next.