Finding Nature

A PIPTree invariant

This is a rather straightforward proof. We rely heavily on the fact that the prefix is an ECF and the ECF is defined by a reduced trajectory, and all reduced trajectories terminate with an odd number.

Let us begin by considering a parent node $n$ with prefix $\{p_0, p_1, \ldots, p_m\}$. The corresponding ICF is as follows:

$$n = n_m\frac{2^{p_{m}}}{3^{m}} - \frac{2^{p_{m-1}}}{3^{m}} - \frac{2^{p_{m-2}}}{3^{m-1}} - \ldots - \frac{2^{p_1}}{3^2} - \frac{2^{p_0}}{3^1}$$

Good Parent

Now, suppose that this parent node has good nature 🟢, denote the number at left and right children as $g_L$ and $g_R$ respectively. The resulting ICFs are:

$$g_L = g_{L}'\frac{2^{p_r}}{3^{m+1}} - \frac{2^{p_{m}-1}}{3^{m+1}} - \frac{2^{p_{m-1}-1}}{3^{m}} - \frac{2^{p_{m-2}-1}}{3^{m-1}} - \ldots - \frac{2^{p_1-1}}{3^2} - \frac{2^{p_0-1}}{3^1}$$

$$g_R = g_R'\frac{2^{p_{m}-1}}{3^{m}} - \frac{2^{p_{m-1}-1}}{3^{m}} - \frac{2^{p_{m-2}-1}}{3^{m-1}} - \ldots - \frac{2^{p_1-1}}{3^2} - \frac{2^{p_0-1}}{3^1}$$

Now notice that most of the terms on the right side are common, in fact:

$$n - n_m\frac{2^{p_{m}}}{3^{m}}= - \frac{2^{p_{m-1}}}{3^{m}} - \frac{2^{p_{m-2}}}{3^{m-1}} - \ldots - \frac{2^{p_1}}{3^2} - \frac{2^{p_0}}{3^1}$$

We also know that $g_L = n/2+r$ and $g_R = n/2$, so:

$$\frac{n}{2}+2^{p_r} = g_L'\frac{2^{p_r}}{3^{m+1}} -\frac{2^{p_m-1}}{3^{m+1}}+ \frac{1}{2}\left(n - n_m\frac{2^{p_m}}{3^m}\right)$$

$$\frac{n}{2}= g_R'\frac{2^{p_m-1}}{3^m} + \frac{1}{2}\left(n - n_m\frac{2^{p_m}}{3^m}\right)$$

When we leave $g_L'$ and $g_R'$ alone in both equations we get:

$$g_L' = 3^{m+1} + \frac{3n_m + 1}{2^{p_r + 1 - p_m}}$$

$$g_R' = n_m$$

Bad Parent

Now we will do the same for a parent node with bad nature 🔴. Denote the left child as $b_L$ and right child as $b_R$ with the resulting ICFs:

$$b_L = b_L'\frac{2^{p_{m}-1}}{3^{m}} - \frac{2^{p_{m-1}-1}}{3^{m}} - \frac{2^{p_{m-2}-1}}{3^{m-1}} - \ldots - \frac{2^{p_1-1}}{3^2} - \frac{2^{p_0-1}}{3^1}$$

$$b_R = b_{R}'\frac{2^{p_r}}{3^{m+1}} - \frac{2^{p_{m}-1}}{3^{m+1}} - \frac{2^{p_{m-1}-1}}{3^{m}} - \frac{2^{p_{m-2}-1}}{3^{m-1}} - \ldots - \frac{2^{p_1-1}}{3^2} - \frac{2^{p_0-1}}{3^1}$$

Again, we know that $b_L = n/2+r$ and $b_R = n/2$. So:

$$\frac{n}{2}+r = b_L'\frac{2^{p_m-1}}{3^m} + \frac{1}{2}\left(n - n_m\frac{2^{p_m}}{3^m}\right)$$

$$\frac{n}{2} = b_R'\frac{2^{p_r}}{3^{m+1}} - \frac{2^{p_m-1}}{3^{m+1}} + \frac{1}{2}\left(n - n_m\frac{2^{p_m}}{3^m}\right)$$

When we leave $b_L'$ and $b_R'$ alone we get:

$$b_L' = n_m + 3^m2^{p_r+1-p_m}$$

$$b_R' = \frac{3n_m+1}{2^{p_r+1-p_m}}$$

Note that in both bad and good cases, we have the expression $p_r+1-p_m$; this is always a positive integer as $p_m \leq p_r$ by definition of how prefixes change within the PIPTree.

There is a cute relationship between children:

$$b_R' = \frac{3b_L'+1}{2^{p_r+1-p_m}} - 3^{m+1}$$

$$g_L' = \frac{3g_R'+1}{2^{p_r+1-p_m}} + 3^{m+1}$$

Even or Odd

We have defined ECFs over reduced trajectories only, so prefixes should also correspond to trajectories with odd terminating numbers. As such, $g_L', g_R'$ and $b_L', b_R'$ should be odd numbers, if the parent is good or bad respectively.

Note that $n_m$ is a terminating number too, and must be odd by definition. With this, we can observe that $b_L'$ and $g_R'$ are always odd!

Now, notice that $g_L' = 3^{m+1} + b_R'$. So, if $b_R'$ is odd then $g_L'$ is even, or if $b_R'$ is even then $g_L'$ is odd. This means that if $b_R'$ is odd, the node has bad nature; or if $b_R'$ is even, the node has good nature.

All we now care about is whether the following expression is even or odd:

$$\frac{3n_m+1}{2^{p_r+1-p_m}}$$

If you look carefully, this is as if we are doing a reduced Collatz operation $R$. In fact, our node $n$ with prefix $\{p_0, p_1, \ldots, p_m\}$ corresponded to the trajectory:

$$n \xrightarrow{p_0} R_0(n) \xrightarrow{p_1 - p_0} R(n_0) \xrightarrow{p_2 - p_1} R(n_1) \xrightarrow{p_3 - p_2} \ldots \xrightarrow{p_m - p_{m-1}} n_m$$

Now, if the expression above (which is equal to $b_R'$) is an odd number, it can be considered within the following trajectory:

$$n \xrightarrow{p_0} R_0(n) \xrightarrow{p_1 - p_0} R(n_0) \xrightarrow{p_2 - p_1} R(n_1) \xrightarrow{p_3 - p_2} \ldots \xrightarrow{p_m - p_{m-1}} n_m \xrightarrow{p_r+1-p_m} b_R'$$

That is it! Check if $b_R'$ is odd, and if it is, the node is bad; otherwise good.

Invariance

The nature of a node at some index $i$ is always the same, regardless of the size of PIPTree; it is an invariant. How is that possible if we calculated the nature via number and prefix, which is changing?

To see why, consider the effects of going from PIPTree of $k$ to PIPTree of $k+1$.

• Node number $n$ becomes $2n$.
• Node prefix $\{p_0, p_1, \ldots, p_m\}$ becomes $\{p_0+1, p_1+1, \ldots, p_m+1\}$.

Let us look at ICF of $n$ with prefix $\{p_0, p_1, \ldots, p_m\}$:

$$n = n_m\frac{2^{p_{m}}}{3^{m}} - \frac{2^{p_{m-1}}}{3^{m}} - \frac{2^{p_{m-2}}}{3^{m-1}} - \ldots - \frac{2^{p_1}}{3^2} - \frac{2^{p_0}}{3^1}$$

Now, let us look at $2n$ with $\{p_0+1, p_1+1, \ldots, p_m+1\}$:

$$2n = n_m'\frac{2^{p_{m}+1}}{3^{m}} - \frac{2^{p_{m-1}+1}}{3^{m}} - \frac{2^{p_{m-2}+1}}{3^{m-1}} - \ldots - \frac{2^{p_1+1}}{3^2} - \frac{2^{p_0+1}}{3^1}$$

$$2(n) = 2\left(n_m'\frac{2^{p_{m}}}{3^{m}} - \frac{2^{p_{m-1}}}{3^{m}} - \frac{2^{p_{m-2}}}{3^{m-1}} - \ldots - \frac{2^{p_1}}{3^2} - \frac{2^{p_0}}{3^1}\right)$$

$$n = n'_m\frac{2^{p_{m}}}{3^{m}} - \frac{2^{p_{m-1}}}{3^{m}} - \frac{2^{p_{m-2}}}{3^{m-1}} - \ldots - \frac{2^{p_1}}{3^2} - \frac{2^{p_0}}{3^1}$$

Turns out that $n_m' = n_m$.

Although the number and prefix changed for the node in PIPTree, the terminating number did not change. Nature calculation relies on the terminating number, the root prefix $p_r$ and $p_m$ for a given node. Well, $p_r$ and $p_m$ both increased by 1, so their change canceled out too! As a result, the nature of a node does not change with respect to PIPTree size.

The root node is always good. The number is $n=2^{p_r}$ with prefix $\{p_r\}$. As such, the terminating number of this trajectory is 1 (i.e. $n_m = 1$). So:

$$b_R'=\frac{3n_m+1}{2^{p_r+1-p_m}}=\frac{4}{2}=2$$

which is an even number.