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 nn with prefix {p0,p1,…,pm}\{p_0, p_1, \ldots, p_m\}. The corresponding ICF is as follows:

n=nm2pm3m−2pm−13m−2pm−23m−1−…−2p132−2p031n = 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 gLg_L and gRg_R respectively. The resulting ICFs are:

gL=gL′2pr3m+1−2pm−13m+1−2pm−1−13m−2pm−2−13m−1−…−2p1−132−2p0−131g_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}
gR=gR′2pm−13m−2pm−1−13m−2pm−2−13m−1−…−2p1−132−2p0−131g_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−nm2pm3m=−2pm−13m−2pm−23m−1−…−2p132−2p031n - 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 gL=n/2+rg_L = n/2+r and gR=n/2g_R = n/2, so:

n2+2pr=gL′2pr3m+1−2pm−13m+1+12(n−nm2pm3m)\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)
n2=gR′2pm−13m+12(n−nm2pm3m)\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 gL′g_L' and gR′g_R' alone in both equations we get:

gL′=3m+1+3nm+12pr+1−pmg_L' = 3^{m+1} + \frac{3n_m + 1}{2^{p_r + 1 - p_m}}
gR′=nmg_R' = n_m

Bad Parent

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

bL=bL′2pm−13m−2pm−1−13m−2pm−2−13m−1−…−2p1−132−2p0−131b_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}
bR=bR′2pr3m+1−2pm−13m+1−2pm−1−13m−2pm−2−13m−1−…−2p1−132−2p0−131b_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 bL=n/2+rb_L = n/2+r and bR=n/2b_R = n/2. So:

n2+r=bL′2pm−13m+12(n−nm2pm3m)\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)
n2=bR′2pr3m+1−2pm−13m+1+12(n−nm2pm3m)\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 bL′b_L' and bR′b_R' alone we get:

bL′=nm+3m2pr+1−pmb_L' = n_m + 3^m2^{p_r+1-p_m}
bR′=3nm+12pr+1−pmb_R' = \frac{3n_m+1}{2^{p_r+1-p_m}}

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

There is a cute relationship between children:

bR′=3bL′+12pr+1−pm−3m+1b_R' = \frac{3b_L'+1}{2^{p_r+1-p_m}} - 3^{m+1}
gL′=3gR′+12pr+1−pm+3m+1g_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, gL′,gR′g_L', g_R' and bL′,bR′b_L', b_R' should be odd numbers, if the parent is good or bad respectively.

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

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

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

3nm+12pr+1−pm\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 RR. In fact, our node nn with prefix {p0,p1,…,pm}\{p_0, p_1, \ldots, p_m\} corresponded to the trajectory:

n→p0R0(n)→p1−p0R(n0)→p2−p1R(n1)→p3−p2…→pm−pm−1nmn \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 bR′b_R') is an odd number, it can be considered within the following trajectory:

n→p0R0(n)→p1−p0R(n0)→p2−p1R(n1)→p3−p2…→pm−pm−1nm→pr+1−pmbR′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 bR′b_R' is odd, and if it is, the node is bad; otherwise good.

Invariance

The nature of a node at some index ii 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 kk to PIPTree of k+1k+1.

  • Node number nn becomes 2n2n.

  • Node prefix {p0,p1,…,pm}\{p_0, p_1, \ldots, p_m\} becomes {p0+1,p1+1,…,pm+1}\{p_0+1, p_1+1, \ldots, p_m+1\}.

Let us look at ICF of nn with prefix {p0,p1,…,pm}\{p_0, p_1, \ldots, p_m\}:

n=nm2pm3m−2pm−13m−2pm−23m−1−…−2p132−2p031n = 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 2n2n with {p0+1,p1+1,…,pm+1}\{p_0+1, p_1+1, \ldots, p_m+1\}:

2n=nm′2pm+13m−2pm−1+13m−2pm−2+13m−1−…−2p1+132−2p0+1312n = 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(nm′2pm3m−2pm−13m−2pm−23m−1−…−2p132−2p031)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=nm′2pm3m−2pm−13m−2pm−23m−1−…−2p132−2p031n = 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 nm′=nmn_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 prp_r and pmp_m for a given node. Well, prp_r and pmp_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=2prn=2^{p_r} with prefix {pr}\{p_r\}. As such, the terminating number of this trajectory is 1 (i.e. nm=1n_m = 1). So:

bR′=3nm+12pr+1−pm=42=2b_R'=\frac{3n_m+1}{2^{p_r+1-p_m}}=\frac{4}{2}=2

which is an even number.

PreviousPath-Indexed Prefix TreeNextParent & Child

Last updated