3.1 Definitions
The compact Collatz map \(T: \mathbb {N} \to \mathbb {N}\) is defined by
where \(X(n) = n \pmod2\).
\(T(n)\) was independently introduced by Terras (1976) [ 6 ] and Everett (in an equivalent form, 1977) [ 3 ] . It is also called the Syracuse map.
One of the advantages of using \(T\) instead of \(C\) or \(R\) is that the number of divisions by 2 per step is the same, regardless if \(n\) is even or odd. This leads to formulae for \(T^i(n)\) that can be handled better, although they are still not closed in the usual sense.
If \(n\) is even, \(T(n) = n/2\).
If \(n\) is even, \(X(n) = 0\), so \(T(n) = (n \cdot 3^0 + 0) / 2 = n/2\).
If \(n\) is odd, \(T(n) = (3n + 1)/2\).
If \(n\) is odd, \(X(n) = 1\), so \(T(n) = (n \cdot 3^1 + 1) / 2 = (3n + 1)/2\).
For any \(k \in \mathbb {N}\), the \(k\)-fold iteration of the map \(T\) is defined recursively by \(T^0(n) = n\) and \(T^{k+1}(n) = T(T^k(n))\).
If \(n \ge 1\), then \(T(n) \ge 1\).
If \(n\) is even, \(n \ge 2\), so \(n/2 \ge 1\). If \(n\) is odd, \(3n+1 \ge 4\), so \((3n+1)/2 \ge 2\).
If \(n \ge 1\), then \(T^k(n) \ge 1\) for all \(k \in \mathbb {N}\).
By induction on \(k\), using Lemma 78.
For any \(k, m, n \in \mathbb {N}\), if \(m \equiv n \pmod{2^{k+1}}\), then \(T(m) \equiv T(n) \pmod{2^k}\).
Let \(m \equiv n \pmod{2^{k+1}}\). This implies \(m \equiv n \pmod2\), so \(X(m) = X(n)\). We have \(2 T(m) = 3^{X(m)} m + X(m)\) and \(2 T(n) = 3^{X(n)} n + X(n)\). Subtracting these yields \(2(T(m) - T(n)) = 3^{X(m)}(m - n)\). Since \(2^{k+1} \mid (m - n)\), we have \(2^k \mid (T(m) - T(n))\).
The number of odd steps in the first \(k\) iterations of \(T\) starting from \(n\) is defined by
The stopping time \(\sigma (n)\) of \(n\) under \(T\) is the smallest \(k \ge 1\) such that \(T^k(n) {\lt} n\). If no such \(k\) exists, \(\sigma (n) = \infty \).
The total stopping time \(\sigma _\infty (n)\) of \(n\) under \(T\) is the smallest \(k \ge 1\) such that \(T^k(n) = 1\). If no such \(k\) exists, \(\sigma _\infty (n) = \infty \).