Terras Theorem 1.1

In Theorem 1.1 of his 1975 paper [5], Terras states that the -th iterate of T(n) , as presented in our introduction,

$T(n) = \left\lbrace \begin{array}{ll} (3n+1)/2 & \mbox{if $n$ is odd} \\ n/2 & \mbox{if $n$ is even} \end{array} \right.$

can be expressed as a "remainder representation" of the form

$T^i(n) = \lambda_i(n) \cdot n + \varrho_i(n)$

where T^i(n) represents $T(T( \ldots T(n)))$ , applied times, and T^0(n)=n . He then goes to define

$X_i(n) &= T^i(n) \mathrm{\ mod\ } 2 & (\mbox{often referred to as Terras'}~\textbf{parity vector}) \\[1em] S_i(n) &= X_0(n) + X_1(n) + \ldots + X_{i-1}(n) & (i \mbox{ of them}) \\[1em] \lambda_i(n) &= \frac{3^{S_i(n)}}{2^i} \\[1em] \varrho_i(n) &= \frac{\lambda_i(n)}2 ~\left( \frac{X_0(n)}{\lambda_1(n)} + \frac{X_1(n)}{\lambda_2(n)} + \ldots + \frac{X_{i-1}(n)}{\lambda_i(n)} \right)$

We shall attempt here to rewrite this "remainder representation" as the same statement as equation (1) in our introduction, appearing in the 1978 paper [2] by Böhm and Sontacchi (as Proposition 7),

$n = \frac{2^{a_m} - \left( 2^{a_{m-1}} 3^0 + 2^{a_{m-2}} 3^1 + \ldots + 2^{a_1} 3^{m-2} + 2^{a_0} 3^{m-1} \right)}{3^m} \qquad (1)$

for any number that does arrive at by the iteration of the Collatz function.

Recall that we defined an integer and constants $c_0, c_1, c_2, \ldots, c_m$ , with $c_0 \ge 0$ and $c_1, c_2, \ldots, c_m > 0$ , that represent the steps taken by iterations of the original Collatz function as it goes from to :

First, steps of the rule are applied (possibly zero);
then one step of the rule ;
then steps of the rule ;
then another step of the rule ;
then steps of the rule ;
...
ending with a final step of the rule ,
and steps of the rule .

The constant represents the number of times the 3n+1 rule was applied during the entire trajectory of from to .

We also defined constants a_i as partial sums of the c_i ( a_0 = c_0 , ~a_1 = c_0+c_1 , ~a_2=c_0+c_1+c_2 , etc.).

Back to Terras, he uses a "shortcut" and applies the mapping (3n+1)/2 to odd numbers. Therefore, a trajectory of from to is shorter (by steps) than a similar trajectory of the original function.

(If the total steps were $m + c_0 + c_1 + \ldots + c_m$ for the function , there are only $c_0 + c_1 + \ldots + c_m$ steps when using the function .)

So we have $a_m = c_0 + c_1 + \ldots + c_m$ representing the total number of applications of the function , starting from and until reaching .

Notice that $a_0, a_1, \ldots, a_m$ are precisely the m+1 positions in the vector where it contains a value of (the times the (3n+1)/2 rule was used, plus the very last element $X_{a_m}$ corresponding to our arrival at ).

Armed with all these definitions, we have

$S_{a_m}(n) &= X_0(n) + X_1(n) + \ldots + X_{a_m-1}(n) = m & (\mbox{how many odd numbers we had in the trajectory } \textbf{before} \mbox{ reaching }1) \\[1em] \lambda_{a_m}(n) &= \frac{3^m}{2^{a_m}} \\[1em] \lambda_{a_i+1}(n) &= \frac{3^{X_{a_0}(n) + X_{a_1}(n) + X_{a_2}(n) + \ldots + X_{a_i}(n)}}{2^{a_i+1}} = \frac{3^{i+1}}{2^{a_i+1}} & (\mbox{we can eliminate the terms where the vector } X \mbox{ contains a } 0) \\[1em] \varrho_{a_m}(n) &= \frac{3^m}{2^{a_m+1}}~ \left( \frac{X_{a_0}(n)}{\lambda_{a_0+1}(n)} + \frac{X_{a_1}(n)}{\lambda_{a_1+1}(n)} + \ldots + \frac{X_{a_{m-1}}(n)}{\lambda_{a_{m-1}+1}(n)} \right) \\[0.5em] &= \frac{3^m}{2^{a_m+1}} ~\left( \frac{2^{a_0+1}}{3^1} + \frac{2^{a_1+1}}{3^2} + \ldots + \frac{2^{a_{m-1}+1}}{3^m} \right) \\[1em] &= \frac{3^{m-1}}{2^{a_m-a_0}} + \frac{3^{m-2}}{2^{a_m-a_1}} + \ldots + \frac{3^0}{2^{a_m-a_{m-1}}}$

and finally, since

$1 &= T^{a_m}(n) = \lambda_{a_m}(n) \cdot n + \varrho_{a_m}(n) \\[0.5em] n &= \frac{1 - \varrho_{a_m}(n)}{\lambda_{a_m}(n)}$

we end up having

$n &= \frac{2^{a_m}}{3^m} \left( 1 - \left( \frac{3^{m-1}}{2^{a_m-a_0}} + \frac{3^{m-2}}{2^{a_m-a_1}} + \ldots + \frac{3^0}{2^{a_m-a_{m-1}}} \right) \right) \\[1em] &= \frac{2^{a_m} - \left( 2^{a_0} 3^{m-1} + 2^{a_1} 3^{m-2} + \ldots + 2^{a_{m-1}} 3^0 \right)}{3^m}$

which is precisely equation (1) above.

$\square$