A Collatz-like mapping based on modulo 4: do all numbers loop or diverge?
问题内容
I have designed a new variant of the Collatz conjecture based on modulo 4 remainders, and I am looking for computational data or heuristic analysis regarding its convergence.
Definition of the Mapping
Let $n$ be a positive integer. We define the transition function $g(n)$ as follows based on $n \pmod 4$:
$$g(n) = \begin{cases} \frac{n}{4} & \text{if } n \equiv 0 \pmod 4 \\ 3n + 1 & \text{if } n \equiv 1 \pmod 4 \\ \frac{n}{2} & \text{if } n \equiv 2 \pmod 4 \\ 3n - 1 & \text{if } n \equiv 3 \pmod 4 \end{cases}$$
Observed Behavior & Trivial Cycle
For small values, most numbers seem to quickly hit the trivial cycle: $$\mathbf{4 \to 1 \to 4 \to 1 \dots}$$
For example, starting with $n = 5$:
- $5 \equiv 1 \pmod 4 \implies g(5) = 3(5)+1 = 16$
- $16 \equiv 0 \pmod 4 \implies g(16) = 16/4 = 4$
- $4 \equiv 0 \pmod 4 \implies g(4) = 4/4 = 1$
- $1 \equiv 1 \pmod 4 \implies g(1) = 3(1)+1 = 4$
A Fascinating Example: The Mersenne Number $M_{13} = 8191$
I specifically tested the Mersenne number $8191$ (which is $\equiv 3 \pmod 4$). It undergoes a wild sequence of expansion and contraction before surprisingly collapsing back to 1 in 30 steps: $8191 \to 24572 \to 6143 \to 18428 \to 4607 \to 13820 \to 3455 \to 10364 \to 2591 \to 7772 \to 1943 \to 5828 \to 1457 \to 4372 \to 1093 \to 3280 \to 820 \to 205 \to 616 \to 154 \to 77 \to 232 \to 58 \to 29 \to 88 \to 22 \to 11 \to 32 \to 8 \to 2 \to 1$.
Heuristic Concern
Heuristically, when $n \equiv 1 \pmod 4$, $3n+1$ is always $\equiv 0 \pmod 2$. If it lands on $\equiv 2 \pmod 4$, it is only divided by 2, yielding an overall growth multiplier of roughly $\frac{3}{2}$. If it lands on $\equiv 0 \pmod 4$, it gets divided by 4, yielding a multiplier of $\frac{3}{4}$. Because of the $\frac{3}{2}$ branches, I suspect that some numbers might escape to infinity.
My Questions
- Has this exact $\pmod 4$ mapping been studied before? If so, what is it called?
- Does anyone have a script (Python/C++) that can check up to $10^9$ or higher to find the first counterexample that either diverges to infinity or falls into a non-trivial cycle other than $\{1, 4\}$?
I would appreciate any computer search results or probabilistic proofs regarding the behavior of this system!
回答 (1)
The map is actually quite easy to prove convergent, because every odd step is followed by a forced division by $4$.
Let
$$ g(n)= \begin{cases} n/4 & n\equiv 0 \pmod 4,\\ 3n+1 & n\equiv 1 \pmod 4,\\ n/2 & n\equiv 2 \pmod 4,\\ 3n-1 & n\equiv 3 \pmod 4. \end{cases} $$
If $n$ is even and $n>1$, then either
$$ g(n)=n/2 $$
or
$$ g(n)=n/4, $$
so in either case $g(n)<n$.
Now suppose $n$ is odd.
If $n\equiv 1 \pmod 4$, write $n=4k+1$. Then
$$ g(n)=3(4k+1)+1=12k+4=4(3k+1), $$
so
$$ g^2(n)=3k+1=\frac{3n+1}{4}. $$
For $n>1$, we have $k\ge 1$, hence
$$ 3k+1<4k+1=n. $$
Thus $g^2(n)<n$.
Similarly, if $n\equiv 3 \pmod 4$, write $n=4k+3$. Then
$$ g(n)=3(4k+3)-1=12k+8=4(3k+2), $$
so
$$ g^2(n)=3k+2=\frac{3n-1}{4}. $$
Again,
$$ 3k+2<4k+3=n. $$
Thus $g^2(n)<n$.
Therefore every positive integer $n>1$ decreases after at most two applications of $g$. By infinite descent, every positive orbit eventually reaches $1$. Since
$$ 1\mapsto 4\mapsto 1, $$
the only positive cycle is the trivial cycle $\{1,4\}$.