---
description: A PIPTree invariant
---

# Finding Nature

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.

{% hint style="info" %}
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}
$$
{% endhint %}

## 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](../../introduction#reducing-to-odd-numbers) $$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$$.&#x20;

* 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$$.&#x20;

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.

{% hint style="info" %}
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.
{% endhint %}
