Proof for simplified Collatz conjecture variant with $10^{10^{100}} + 1$ as increment

Question

Given the function

$$ S(n) = \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \\ n + 1, & \text{if $n$ is odd} \end{cases} $$

Prove the conjecture: for any positive integer $n$, if you apply the function $S(n)$ repeatdly, it will eventually reach 1.

To prove this you just need to combine the $n + 1$ and the $\frac{n}{2}$ steps, as an odd number when added an odd number always become even.

$$ S(n) = \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \\ \frac{n + 1}{2}, & \text{if $n$ is odd} \end{cases} $$

This way you just need to prove that the output of the function is always smaller than the input for any value bigger than 1, because the value will become smaller and smaller when applying the function which means that it will eventually reach the minimun value (1).

Case 1: $\frac{n}{2} < n \implies n < 2n \implies 0 < n \implies n > 0 \implies n > 1$

Case 2: $\frac{n + 1}{2} < n \implies n + 1 < 2n \implies 1 < n \implies n > 1$

Which proves the conjecture.

My question is about when the increment is a huge number

$$ S(n) = \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \\ \frac{n + 10^{10^{100}} + 1}{2}, & \text{if $n$ is odd} \end{cases} $$

How can one prove any starting positive integer will reach a loop? (It might have multiple loops)

Answer 1

For $$ S(n) = \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \\ n + 1 & \text{if $n$ is odd} \end{cases} $$

All you need to prove is that for $n \ge 2$ there will be an element less than $n$ in the sequence. And that is obviously the case since $\frac{n}{2} < n$ and $\frac{n + 1}{2} < n$ for any $n \ge 2$

---

For $$ S(n) = \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \\ n + k & \text{if $n$ is odd} \end{cases} $$

With your huge odd increment $k$, two steps give $\frac{n + k}{2}$ which is less than $n$ if $n > k$. So the sequence shrinks until $n \le k$, and remains $\le k$. Since there is a finite number of values $n \le k$ the sequence must repeat.

On the other hand $n \ge \frac{k}{2}$ after each step so it’s not going to reach $n = 1$ or any $n < \frac{k}{2}$ ever.

Answer 2

For your Collatz system we can prove:

1. Every odd integer $n \le k$ is a member of a cycle whose odd integers are all $\le k$.
2. The total number of divide by $2$'s in traversing all cycles once $=k$.

To show that (1) is true, consider the sequence of odd integers given by $$n_{i+1} = \frac{n_i + k}{2^{d_i}}$$ where $d_i$ is the unique integer such that $n_{i+1}$ is an odd integer. For every $n_{i+1} \le k$, there is at most one one $n_i \le k$ such that $n_{i+1} \le k$. To show this, assume there are distinct $n_i$ and $n'_i$ that meet this condition. Then $$n_{i+1} = \frac{n_i + k}{2^{d_i}} = \frac{n'_i + k}{2^{d'_i}}$$ Without loss of generality assume that $n_i < n'_i$ and hence $d_i < d'_i$, then $$n'_i + k = 2^{d'_i-d_i} (n_i + k) \ge 2(1+k)$$ so that $n'_i > k$. Therefore, each $n_i \le k$ has exactly one immediate preceding $n_{i-1} \le k$ (and of course exactly one following $n_{i+1}$) and since there are a finite number of $n_i \le k$ each one is part of a cycle.

(2) can be stated as $$S(k) := \sum\limits_{n_i \le k}d_i = k$$ Define $Z(x) := $ the power of 2 in the prime factorization of $x$. $S(k) = \sum{d_i} = \sum{Z(n_i + k)}$. For example $S(1) = Z(2) = 1$, $S(3) = Z(4) + Z(6) = 3$, $S(5) = Z(6) + Z(8) + Z(10) = 5, S(7) = Z(8) + Z(10) + Z(12) + Z(14) = 7$. In general, $S(k+2) = S(k) + Z(2k) + Z(2(k - 1)) - Z(k - 1)$. Note that $Z(2k) = 1$ since $k$ is odd and $Z(2(k-1)) - Z(k-1) = 1$ which gives $S(k+2) = S(k) + 2$. Therefore, since $S(1) = 1$, $S(k) = k$ for all odd $k$.

(1) can also be proven using Euler's Theorem.