Does the truth of one imply the other? A simple Collatz generalization in terms of primes.

Question

Let $f_i:\mathbb{N} \to\mathbb{N}$. The Collatz function states that the following iterated map will eventually equal to 1:

$$f_0(n) = \begin{cases} n/2, & \text{if}\ 2\mid n\\ 3n+1, & \text{otherwise} \\ \end{cases}$$

Noting that $2$ and $3$ are the first two primes I extended the Collatz conjecture prime by prime in the following way:

First extension $$f_1(n) = \begin{cases} n/2, & \text{if}\ 2\mid n\\ n/3, & \text{if}\ 3\mid n\\ 5n+1, & \text{otherwise} \\ \end{cases}$$

Second extension:  $$f_2(n) = \begin{cases} n/2, & \text{if}\ 2\mid n\\ n/3, & \text{if}\ 3\mid n\\ n/5, & \text{if}\ 5\mid n\\ 7n+1, & \text{otherwise} \\ \end{cases}$$

Third extension 

$$f_3(n) = \begin{cases} n/2, & \text{if}\ 2\mid n\\ n/3, & \text{if}\ 3\mid n\\ n/5, & \text{if}\ 5\mid n\\ n/7, & \text{if}\ 7\mid n\\ 11n+1, & \text{otherwise} \\ \end{cases}$$ ....and so on.

Surprisingly, or not so surprisingly, I ran a small test on this generalization for $n\leq40,000$ and found that for the first and second extensions, all numbers return to 1 but for the third extension a single cycle results when $n = 17$, that is, $17 \to 188 \to 94 \to 47 \to 518 \to 259 \to 37 \to 408 \to 204 \to 102 \to 51 \to 17$.

My motivation for this generalization is this paper showing a link between Collatz and primes (see page 10).

Questions:

1. Has such generalization been studied before? Does it even make sense?
2. If the Collatz problem, $3n +1$, has no unbounded/diverging trajectory, does that imply the same for the extensions? Or how does one go about proving or disapproving this assertions?

For my second question, I am leaning 'yes' because having more primes to divide by would only shrink the trajectory toward 1 faster; besides, if we divide any natural number by all primes that it is divisible by, as many times as possible, the transformation shrinks to 1 due to the Fundamental Theorem of Arithmetic.

Answer 1

Here I'll give a helpful scheme of notation for the analysis of existence of cycles, which is a simple generalization of that same scheme which I used for the discussion of the cycles in the Collatz-problem.

Notation

Let us introduce the notation for the extraction of primefactors from a number $n$: $$ \{n\}_{2,3,5,7} : \text{ extracts all primefactors $2,3,5,7$ from $n$} \tag {1.a} $$ We would also write the relevant primefactors of $n$: $$ n=2^A 3^B 5^C 7^D m \implies m=\{n\}_{2,3,5,7} \tag {1.2}$$

---

For a 1-step-transformation we may write: $$ b= \{11a+1\}_{2,3,5,7} \\ \text{ or } \\ b\cdot 2^A3^B5^C7^D = 11 a+1 \tag {2.1} $$ Note, that values of $b$ cannot have the primefactors $(2,3,5,7)$, but even more, cannot have the primefactor $11$.
If we discuss cycles, and $a=b$ then this is also valid for $a$, and thus: $$ \text{no member $a,b,c,...$ of a cycle can have a primefactor $(2,3,5,7,11)$} \tag {2.2}$$

---

Existence of cycles

Existence of 1-step-cycles

For a 1-step-cycle $b=a$ from (2.1) thus follows $$ a\cdot 2^A3^B5^C7^D = 11 a+1 \\ a ( 2^A3^B5^C7^D - 11) = 1 $$ $$ a = {1 \over 2^A3^B5^C7^D - 11} \tag {3.1}$$

Theorem 1: Solutions for 1-step cycle are: $$ a = 1 \qquad \text{for} (A,B,C,D)=(2,1,0,0)\\ a =-1 \qquad \text{for} (A,B,C,D)=(1,0,1,0)\\ $$

---

Existence of 2-step-cycles
For a 2-step cycle we'll have $2$ members $a,b$. $$ b= \{11a+1\}_{2,3,5,7} \qquad a= \{11b+1\}_{2,3,5,7}$$ For the following we assume $a \lt b$ (and in generalizations for more steps: $a$ is the minimal element)

It is not so simple as before, but a "product-equation" can be stated: $$ a \cdot b = \{11a+1\}_{2,3,5,7} \cdot \{11b+1\}_{2,3,5,7} \tag{4.1}$$ from which the following can be formulated: $$ a b \cdot 2^{A_1+A_2}3^{B_1+B_2}5^{C_1+C_2}7^{D_1+D_2} = (11 a+1)(11 b+1) \tag {4.2} $$ $$ 2^{A_1+A_2}3^{B_1+B_2}5^{C_1+C_2}7^{D_1+D_2} = (11 +1/a)(11 +1/b) \tag {4.3}$$ where the rhs must remain integer and equal to a valid expression in the lhs, which has the additional restriction that at least $A_1+A_2 \ge 2$ because by each transfromation-step (at least) one primefactor $2$ occurs.
We can reformulate the rhs a bit more: $$ \qquad\qquad\qquad =121+11(\frac1a+\frac1b)+\frac1a\frac1b $$ $$ \qquad\qquad\qquad =121+{11(a+b)+1 \over ab} \tag {4.4} $$

We see by the fractional term in (4.4), that $a,b$ have upper bounds, because with sufficiently increase of $a$ and $b$, the last term in the rhs decreases below $1$ and shall be unconditionally fractional, preventing any further solution for the 2-step cycles in integers.

For instance, heuristically,

• assuming $a=13$ we find, that $13 \lt b \le 71$,
• assuming $a=17$ we find, that $17 \lt b \le 31$,
• assuming $a=19$ we find, that $19 \lt b \le 23$,
• and find that no further test is needed.

Thus we have only to test few cases for $(a,b)$.

Heuristically, all that cases lead to fractional values in the rhs, so ...

Theorem 2: no $2$-step-cycle is possible.

---

Existence of 3- and more steps cycles

This can be generalized in the obvious way, but which I did not expand here. For $3,4,5$ or other small number step-cycles, I think this can be done in Pari/GP by direct examination of not too many cases. My intention with this all is just to give a tool for a more algebraic analysis of this problem, which immediately allows generalization to other sets of primes-to-be-extracted.

---

Further disproving of N-step-cycles and reducing searchspace
Equation(4.3) gives a tool to estimate a mean-value for all members $(a,b,c,...n)$ of a N-step cycle.
For instance for $N=3$ and asking for a mean value $x$ of all members, we have $$ 2^{S_2}3^{S_3}5^{S_5}7^{S_7} = (11 +\frac1x)^N \tag {5.1}$$ (where we write $S_2$ for $A_1+A_2+A_3$, $S_3$ for $B_1+B_2+B_3$ and so on) and there must exist a lowest number above $L>11^N$ which has only primefactors as on the left hand side. We introduce the notation $$ L=\text{valid_lhs}(x) : \min(L>x: \{L \in \mathbb N \}_{2,3,5,7}=1 \land \nu_2(L) \ge N) \tag {5.2}$$

The last condition is required because we know by the above analysis, that the primefactor $2$ has to occur at least with exponent $N$.

So let's assume there is a $$L=\text{valid lhs}(11^N) \gt 11^N \tag {5.2a} $$ and from the ansatz with an unknown average-value $x$ $$ L = 2^{S_2}3^{S_3}5^{S_5}7^{S_7} = (11 +\frac1x)^N$$ we calculate $x$ $$ L^{1/N} = (11 +1/x) \\ L^{1/N} -11 = 1/x $$ and $$ x= {1 \over L^{1/N} -11} \tag {5.3} $$

As $x$ is a mean value of all involved members of a cycle (here $(a,b,c)$) and we assume always $a$ being the minimal member, we know that $a \lt x$.

Our searchspace for finding the smallest member of an assumed N-step-cycle $a$ is thus now nicely bounded from above, and sometimes that result shows immediately that a cycle cannot exist: since if for some $N$ we get that $x<13$ then $a$ must be smaller than $13$ but there is no number free of the primefactors $(2,3,5,7,11)$ below $13$ .

Of course, this is except $1$ - but for the current set of primes $(2,3,5,7)$ this meaned we'd heve the 1-step-cycle and $a=b=c=1$, which is what we exclude here.

A short heuristic:

N    x                upper bound for a
------------------------------------------
2     3.18767264271       1       no 2 step cycle
3    28.0137896567       23       -case test for a=13,17,19,23 required-
4    11.2502716388        1       no 4 step cycle
5   319.854255596       317       -case test up to a=317 required-
6   147.732223336       139       -case test up to a=139 required-
7   114.725982882       113       -case test up to a=113 required-
8   247.003937577       247       -case test up to a=247 required-
 ... ...              ...

---

For the first few generalizations $f_2()$ to $f_{11}()$

Here the so-far found cycles for some generalizing $f_k()$ (the searchspace for initial $a$ (or better: $a_1$) is up to some 100 000 although very likely this is not needed when looking at the small table above):

      "selection    multi     document of found cycles
        primes"     plicator
-----------------------------------------------------------
f_1()  [2,3,      ] [ 5]:  no cycle found
f_2()  [2,3, 5    ] [ 7]:  no cycle found
f_3()  [2,3, 5,  7] [11]:  3-step: 17 \to 47 \to ... \to 17
f_4()  [2, ..., 11] [13]:  4-step: 19 \to 31 \to ... \to 19
f_5()  [2, ..., 13] [17]: 22-step: 43 \to 61 \to ... \to 43
f_6()  [2, ..., 17] [19]: 16-step: 46063 \to 437599 \to ... \to 46063
f_7()  [2, ..., 19] [23]:  4-step: 179 \to 2059 \to ... \to 179
f_8()  [2, ..., 23] [29]: no cycle found
f_9()  [2, ..., 29] [31]: 30-step: 67 \to 1039 \to ... \to 67
f_10() [2, ..., 31] [37]: 17-step: 2173 \to  5743 \to ... \to 2173
f_11() [2, ..., 37] [41]: no cycle found

---

Conclusion

The algebraic tools shown here are easily extensible for your type of generalization to more primes in the primeslist $(2,3,5,7)$ without needing any modification.

Moreover, surely more of that tools of the $3x+1$-analysis can be adapted for this $3x+1$-extensions, but before going into deeper water, I'll wait whether this all here has been found helpful or you'll go further on your own...

---

P.S.: I don't know whether this formalism also helps for the discussion of the existence of a divergent trajectory.