A formula for building other collatz-like mappings similar to the original 3x + 1.

collatz conjecturedynamical systemsmodular arithmeticnumber theory

I've spent the last couple of weeks searching for papers related to constructing other Collatz-like mappings in the way that I've discovered. I've either come up short or found papers that were way over my head in terms of my ability to comprehend the high level mathematics involved. That being said, I want to introduce a couple ideas I've been playing with and see if anyone in the Stack Exchange community has any feedback or criticism! Odds are that this has already been done, but no harm in rediscovering math!

So, if we generalize the original Collatz mapping and add some variables to replace the constants involved in the multiplication, addition, and division, we might get something like this (I apologize in advance for the LaTex):

If $n \equiv 0 \pmod{d}$:

\begin{align}
f\left(n\right)_{next}=\ \frac{n}{d}\
\end{align}

Otherwise:

\begin{align}
f\left(n\right)_{next}=\ a*n + b\
\end{align}

To represent the original Collatz mapping, we would set the variables as follows:
$a=3$, $b=1$, $d=2$

This gives us the classic $3x+1$ problem. However, we could set these variables to different numbers or functions in order to get other "Collatz-like" mappings, which is exactly what I've done and will describe below.

The "+1"

I think we often obsess over the $+1$ operation in the Collatz mapping. Since it is what "moves the function forward in time". I don't often see many results exploring what happens when we tweak it. If it is tweaked, often it is just replaced with a constant, e.g. $5x+3$ or $7x+5$. More often than not, these alternative mappings tend to go off to infinity or wind up looping back on themselves. I think this is partly because in the original $3x+1$, the $+1$ step has a crucial effect on the sequence: it ensures that the next number in the sequence is divisible by 2. This ensures that after every $3x+1$ step, there is a division by $2$ that occurs. This got me thinking:

What if we replace the $b$ variable with an operation whose purpose is to ensure that the next number in the sequence is divisible by $d$? In other words, the increment function becomes:

\begin{align}
f\left(n\right)_{next}=\ a*n + (d – (a*n \mod{d}))\
\end{align}

You can see that in the original $3x+1$ problem, this change has no effect on the mappings output since:
If $(2 – (a*n \mod{2}) = 1$, nothing changes, we simply add 1. However, it does have some interesting effects on some other Collatz-like mappings.

Behaviors of Alternative Mappings

Using the new version of the increment function above, I've found some interesting behavior for different values for $a$ and $b$ when applying the resulting Collatz-like map. Note that when applying these new maps, I stopped when one of the following occurred:

  1. I reached a number in the sequence that was below the starting value (i.e we found a stopping time).
  2. I reached the starting number (i.e. the sequence had looped back on itself).
  3. I had iterated the function 1000 times (I observed that in most of these cases the values were blowing up to infinity).

I will lay them out in a table below. Note that I only used starting values of up to 10,000 (a mere drop in the bucket), but I plan to investigate further once I optimize a bit.

\begin{array}{|c|c|c|}
\hline
a & d & \texttt{Notes}\\ \hline
3 & 2 & \text{This is the original Collatz mapping. No loops, and all sequences fall to a value below the initial value.}\\ \hline
4 & 3 & \text{No loops, but every odd number explodes to infinity.}\\ \hline
6 & 5 & \text{No loops and every sequence falls to a value below the initial value.}\\ \hline
6 & 4 & \text{No loops and every sequence falls to a value below the initial value.}\\ \hline
6 & 3 & \text{No loops and every sequence falls to a value below the initial value.}\\ \hline
8 & 7 & \text{No loops and every sequence falls to a value below the initial value.}\\ \hline
9 & 8 & \text{No loops and every sequence falls to a value below the initial value.}\\ \hline
10 & 9 & \text{Loops at 35 and 135, but every other sequence falls to a value below the initial value.}\\ \hline
11 & 10 & \text{Loops at 42 and 420, but every other sequence falls to a value below the initial value.}\\ \hline
11 & 9 & \text{Loops at 10 and 90, but every other sequence falls to a value below the initial value.}\\ \hline
12 & 10 & \text{No loops and every number falls to a value below the initial value.}\\ \hline
\end{array}

Other Notable Behavior Mappings

So it seems that when $a – d = 1$, there are some interesting patterns to be found amongst the stopping times, at least for the first few.

  • The lowest valued stopping time is 1. This is trivial.
  • If $a = 3$ and $d = 2$, integers with stopping time 3 are congruent to $n \equiv 1 \pmod{4}$
  • If $a = 4$ and $d = 3$, integers with stopping time 3 are equal to $n \equiv [2, 4] \pmod{9}$
  • If $a = 5$ and $d = 4$, integers with stopping time 3 are congruent to $n \equiv [3, 6, 9] \pmod{16}$
  • If $a = 6$ and $d = 5$, integers with stopping time 3 are congruent to $n \equiv [4, 8, 12, 16] \pmod{25}$
  • If $a = 7$ and $d = 6$, integers with stopping time 3 are congruent to $n \equiv [5, 10, 15, 20, 25] \pmod{36}$

There is a clear pattern in the way the numbers for a given stopping time is defined. I still plan on investigating this further, but would like to know if this approach has been taken before or anyone knows of similar approaches. Maybe this could give us a branch of mappings to study that could tell us more about the $3x+1$ mapping.

Best Answer

Your post doesn't seem to be asking a clear question, so I will instead point you to references. Your problem is a natural generalization of the Collatz conjecture and has been studied. A good Google scholar search term is "generalized Collatz problem"; see this paper for example.

Wikipedia mentions that the generalized Collatz problem is undecidable, as shown by John H. Conway in 1972. What's even more interesting (Kurtz and Simon, above link, 2007) is that even for a fixed modulus, 6480, it's undecidable. That is, if we only consider Collatz functions $g$ where $g$ is parameterized by $a_0, a_1, \ldots, a_{6479}$ and $b_0, b_1, \ldots, b_{6479}$ and is given by the formula $$ g(n) = a_i n + b_i \text{ if } n \equiv i \pmod{6480}, $$ still the Collatz problem is undecidable: that is on input the parameters $a_i$ and $b_i$, it's undecidable to determine whether or not $g(g(\ldots(n) \ldots))$ is eventually $1$ for all $n$.

Related Question