Back to index

Recall that Terras' parity vector is a sequence of 1's and 0's representing the branches taken by a number during iteration of the T(n) function he uses,

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.

At each iteration, the parity vector X_i(n) of a number n contains a 1 if the number at this stage is odd (so that the (3n+1)/2 rule is used), or it contains a 0 when the number is even (and the n/2 rule applies):

X_i(n) = T^{\,i}(n) \mathrm{\ mod\ } 2

where T^{\,i}(n) is the i-th iteration of the function T(n). We take T^1(n) = T(n), and T^0(n) = n.

If a number n is of the form 2^k s - 1, with s an odd integer and k > 0,

then X_i(n)=1 for 0 \le i < k, and X_k(n)=0.

Moreover, T^k(n) = 3^k s - 1.

X_0(n)=1 because the original number n is odd. Then the (3n+1)/2 rule is applied, resulting in

T^1(n) = \frac{3(2^k s - 1) + 1}{2} = 3^1 \,2^{k-1} s - 1

which has a form similar to the original n, but with one less factor 2 and one more factor 3.

As long as the exponent of 2 is larger than zero, we will continue having an odd number (X_i(n)=1) and be able to apply again the (3n+1)/2 rule.

After k iterations, the exponent of 2 will be consumed, and the number replaced by 3^k s - 1, which is even because s is odd; hence X_k(n)=0.

\square

Note that a number n of the form 2^k s - 1, with s odd, has a binary representation that ends in k bits with a value of ``1, followed to the left by a bit with a value of ``0.
(Because the binary representation of n + 1 = 2^k s will have k ``0 bits at the end, and then the ending bit of s, which is ``1 because s is odd; adding 1 to n toggles these bits.)

This means that the parity vector of n coincides (if laid out right-to-left) with the last k + 1 bits of the binary representation of the number.

Thus we know, for example, that the number 39 (100111 in binary) will take the (3n+1)/2 branch three times before using the n/2 rule, because 39 = 5 \cdot 2^3 - 1.