2.1 Definitions
The reduced Collatz map \(R: \mathbb {N}\to \mathbb {N}\) is defined by
where \(v_2(m)\) is the dyadic valuation of \(m\). In short \(R(n)=\) odd part of \(3n+1\).
This map seems to have been introduced by Crandall [ 1 ] . One of its advantages is that multiplications by 3 are constant for each step, regardless if \(n\) is even or odd.
For any \(k \in \mathbb {N}\), the \(k\)-fold iteration of the reduced Collatz map \(R^k: \mathbb {N} \to \mathbb {N}\) is defined recursively by
and
\(R(0) = 1\).
By definition, \(R(0) = \text{odd part of } (3 \cdot 0 + 1) = \text{odd part of } 1 = 1\).
\(R(1) = 1\).
By definition, \(R(1) = \text{odd part of } (3 \cdot 1 + 1) = \text{odd part of } 4 = 1\).
For all \(n \in \mathbb {N}\), \(R(n) \geq 1\).
Since \(3n + 1 \geq 1\) for all \(n\), the odd part of \(3n+1\) is a positive divisor of a positive number, hence \(R(n) \geq 1\).
For all \(n, i \in \mathbb {N}\) with \(n \geq 1\), we have \(R^i(n) \geq 1\).
We proceed by induction on \(i\). The base case \(i = 0\) is immediate since \(R^0(n) = n \geq 1\). For the inductive step, \(R^{i+1}(n) = R^i(R(n))\). By Lemma 49, \(R(n) \geq 1\), so the induction hypothesis gives \(R^i(R(n)) \geq 1\).
For all \(n \in \mathbb {N}\), \(R(n)\) is odd, i.e. \(R(n) \equiv 1 \pmod{2}\).
By definition, \(R(n)\) is the odd part of \(3n+1\).
For all \(n \in \mathbb {N}\) and \(i \geq 1\), \(R^i(n)\) is odd, i.e. \(R^i(n) \equiv 1 \pmod{2}\).
We proceed by induction on \(i\). The base case \(i = 1\) follows directly from Lemma 51, since \(R^1(n) = R(n)\) is odd. For the inductive step, \(R^{i+1}(n) = R^i(R(n))\). If \(i \geq 1\), the induction hypothesis gives that \(R^i(R(n))\) is odd. If \(i = 0\), then \(R^{i+1}(n) = R^1(n) = R(n)\), which is odd by Lemma 51.
If \(m \equiv 0 \pmod{3}\), then there is no \(n \in \mathbb {N}\) such that \(R(n) = m\). In other words, multiples of \(3\) are not in the image of \(R\).
Suppose for contradiction that \(R(n) = m\) for some \(n\), with \(3 \mid m\). Since \(R(n)\) is the odd part of \(3n+1\), we have \(R(n) \mid 3n+1\).
Let \(m {\gt} 0\) be odd with \(m \not\equiv 0 \pmod{3}\). Then there exists an odd \(n {\gt} 1\) such that \(R(n) = m\).
If \(m = 1\), take \(n = 5\); one checks \(R(5) = 1\) by computation.
If \(m {\gt} 1\), we split on the residue of \(m\) modulo \(3\):
If \(m \equiv 1 \pmod{3}\): set \(n = (4m - 1)/3\). Then \(3 \mid (4m-1)\) and \(3n + 1 = 4m = 2^2 \cdot m\). Since \(m\) is odd, the odd part of \(2^2 \cdot m\) is \(m\), so \(R(n) = m\). One verifies \(n\) is odd and \(n {\gt} 1\).
If \(m \equiv 2 \pmod{3}\): set \(n = (2m - 1)/3\). Then \(3 \mid (2m-1)\) and \(3n + 1 = 2m = 2^1 \cdot m\). Since \(m\) is odd, the odd part of \(2m\) is \(m\), so \(R(n) = m\). One verifies \(n\) is odd and \(n {\gt} 1\).
For any odd \(n {\gt} 0\), \(R(n) {\gt} n\) if and only if \(n \equiv 3 \pmod{4}\).
(\(\Rightarrow \)) Suppose \(n \equiv 1 \pmod{4}\), say \(n = 4k + 1\). Then \(3n + 1 = 12k + 4 = 2^2(3k + 1)\). The reduced step is \(R(n) = \text{odd part of } (3k + 1) \le 3k + 1\). Since \(3k + 1 {\lt} 4k + 1\) (for \(k \ge 0\)), we have \(R(n) {\lt} n\), a contradiction. Thus we must have \(n \equiv 3 \pmod{4}\).
(\(\Leftarrow \)) Suppose \(n \equiv 3 \pmod{4}\), say \(n = 4k + 3\). Then \(3n + 1 = 12k + 10 = 2(6k + 5)\). Since \(6k + 5\) is odd, \(R(n) = 6k + 5\). Since \(k \ge 0\), we have \(6k + 5 {\gt} 4k + 3\), so \(R(n) {\gt} n\).
If \(n {\gt} 0\) is odd and \(R(n) = m\), then there exists \(i \ge 1\) such that \(C^i(n) = m\).
By definition, \(R(n)\) is the odd part of \(3n+1\), so \(3n+1 = 2^k \cdot m\) for some \(k \in \mathbb {N}\). Since \(n\) is odd, \(3n+1\) is even, so \(k \ge 1\). One iteration of the Collatz map on \(n\) gives \(C^1(n) = 3n+1 = 2^k \cdot m\). By Lemma 26, applying the Collatz map \(k\) more times to \(2^k \cdot m\) yields \(C^k(2^k \cdot m) = m\). Thus \(C^{k+1}(n) = C^k(C(n)) = C^k(2^k \cdot m) = m\).
If \(n\) is odd and \(R^k(n) = m\), then there exists \(i \ge k\) such that \(C^i(n) = m\).
We proceed by induction on \(k\). The base case \(k=0\) is trivial as \(R^0(n) = n = C^0(n)\). For the inductive step \(k+1\), let \(n_1 = R(n)\). By the induction hypothesis, since \(R^k(n_1) = m\), there exists \(i \ge k\) such that \(C^i(n_1) = m\). By Lemma 56, there exists \(j \ge 1\) such that \(C^j(n) = n_1\). Then \(C^{i+j}(n) = C^i(C^j(n)) = C^i(n_1) = m\). Since \(i \ge k\) and \(j \ge 1\), we have \(i+j \ge k+1\).
For \(d, n \in \mathbb {N}\), the number of odd steps in the first \(d\) iterations of the standard Collatz map starting from \(n\) is defined by
where \([P]\) is the Iverson bracket.
Let \(n \in \mathbb {N}\) be odd. For any \(d \in \mathbb {N}\), the odd part of \(C^d(n)\) is equal to \(R^k(n)\), where \(k = \text{countOdds}(d, n)\). That is,
We proceed by induction on \(d\). The base case \(d=0\) is trivial as \(C^0(n) = n\) is odd, its odd part is \(n\), and \(\text{count\_ odds}(0, n) = 0\), with \(R^0(n) = n\).
For the inductive step \(d+1\), let \(C^d(n) = m\). By induction, the odd part of \(m\) is \(R^{\text{countOdds}(d, n)}(n)\). If \(m\) is even, then \(C^{d+1}(n) = m/2\). The odd part of \(m/2\) is the same as the odd part of \(m\). Since \(m\) is even, \(\text{countOdds}(d+1, n) = \text{countOdds}(d, n)\), and the equality holds. If \(m\) is odd, then \(C^{d+1}(n) = 3m+1\). Since \(m\) is odd, it equals its own odd part, \(m = R^{\text{countOdds}(d, n)}(n)\). The odd part of \(3m+1\) is \(R(m) = R(R^{\text{countOdds}(d, n)}(n)) = R^{\text{countOdds}(d, n) + 1}(n)\). Since \(m\) is odd, \(\text{countOdds}(d+1, n) = \text{countOdds}(d, n) + 1\), confirming the result.
Let \(n \in \mathbb {N}\) be odd. There exists a cycle in the standard Collatz map starting from \(n\) if and only if there exists a cycle in the reduced Collatz map starting from \(n\).
(\(\Rightarrow \)) Suppose there exists \(k {\gt} 0\) such that \(C^k(n) = n\). By Lemma 59, the odd part of \(C^k(n)\) is \(R^j(n)\) where \(j = \text{countOdds}(k, n)\). Since \(n\) is odd, its odd part is \(n\), so \(R^j(n) = n\). Since \(n\) is odd and \(k {\gt} 0\), at least one standard Collatz step must have occurred, and since \(n \ge 1\), we must have \(j {\gt} 0\). Thus \(n\) is part of a reduced cycle.
(\(\Leftarrow \)) Suppose there exists \(j {\gt} 0\) such that \(R^j(n) = n\). By Lemma 57, there exists \(k \ge j\) such that \(C^k(n) = n\). Since \(j {\gt} 0\), we have \(k {\gt} 0\), so \(n\) is part of a standard cycle.
Let \(n \in \mathbb {N}\) be odd. The orbit of \(n\) under the standard Collatz map is bounded if and only if its orbit under the reduced Collatz map is bounded.
(\(\Rightarrow \)) Suppose there exists \(B\) such that \(C^k(n) \le B\) for all \(k \ge 0\). By Lemma 57, every reduced iterate \(R^j(n)\) is equal to some \(C^k(n)\), so \(R^j(n) \le B\) for all \(j \ge 0\).
(\(\Leftarrow \)) Suppose there exists \(B\) such that \(R^j(n) \le B\) for all \(j \ge 0\). We claim that \(C^k(n) \le \max (n, 3B+1)\) for all \(k \ge 0\). We proceed by induction on \(k\). The base case \(k=0\) is \(C^0(n) = n\), which is clearly bounded. For the inductive step, let \(C^k(n) = m\). If \(m\) is even, \(C^{k+1}(n) = m/2 \le m\), which is bounded by the induction hypothesis. If \(m\) is odd, then by Lemma 59, \(m\) is the odd part of \(C^k(n)\), which is \(R^j(n)\) for \(j = \text{countOdds}(k, n)\). Thus \(m \le B\). Then \(C^{k+1}(n) = 3m+1 \le 3B+1\), which is within the bound.