Recursive Index-Parity Tree

Classifying numbers with respect to their position

So far we have looked at trajectories, their ECFs, and their ICFs. Now, we will describe a binary tree called Recursive Index-Parity Tree (RIPTree) that allows us a great tool to obtain numbers with non-empty prefixes for their sequence ECFs.

RIPTree(16)

A RIPTree for a natural number $n$ is defined as a binary tree with the following properties:

• The root node has a list of natural number $\{1, 2, \ldots, n\}$.

• The left child of every node has the even-indexed elements of its parent's numbers, and the edge between them is labeled as 0.

• The left child of every node has the odd-indexed elements of its parent's numbers, and the edge between them is labeled as 1.

• Empty nodes are omitted.

For instance, if a node has $\{1, 2,3, 4\}$, then its left child has $\{2, 4\}$ and its right child has $\{1, 3\}$.

Path

Path is a function $P : \mathbb{N} \to \mathbb{N}$ such that $P(n)$ is the binary number represented by the concatenation of edge labels that are encountered when we start from the root node and reach the first node that has $n$ as its smallest element.

There is a quite neat formula to calculate $P(n)$:

$$n \xrightarrow{\textrm{subtract 1}} \cdot \xrightarrow{\textrm{reverse}} \cdot \xrightarrow{\textrm{flip bits}} P(n)$$

Noting that every operation here is bijective, we can do the opposite to calculate the number at a given path $p$:

$$P^{-1}(p)\xleftarrow{\textrm{add 1}} \cdot \xleftarrow{\textrm{reverse}} \cdot \xleftarrow{\textrm{flip bits}} p$$

There is even an OEIS entry for the path calculation given $n$, see https://oeis.org/A036044.

The first node that has number 7 as its smallest element is at the path 100. Let's see if our calculations hold:

• $7 = (111)_2$ (Write as Binary)

• 110 (Subtract 1)

• 011 (Reverse)

• 100 (Flip)

Now, going back from 100 to 7:

• 011 (Flip)

• 110 (Reverse)

• 111 (Add 1)

• $(111)_2 = 7$ (Write as Decimal)

The paths of powers of 2 are always all zeros. So the corresponding number is 0, and we won't be able to calculate which power of 2 this belongs to just by looking at the result. We can obtain a 1-to-1 correspondence by appending 1 to the path of powers of 2. Looking at the tree, we notice that appending 1 does not change the first number in the node.

Prefix at Path

Let us look at the list of numbers at a given path, say $\{3, 7, 11, \ldots\}$ at the path 10. Let us look at their sequences:

• $3 \xrightarrow{0} 3 \xrightarrow{1} 5 \xrightarrow{4} 1$ with ECF $\{0, 1, 5\}$.

• $7 \xrightarrow{0} 7 \xrightarrow{1} 11 \xrightarrow{1} 17 \xrightarrow{2} 13 \xrightarrow{3} 5 \xrightarrow{4} 1$ with ECF $\{0, 1, 2, 4, 7, 11\}$.

• $11 \xrightarrow{0} 11 \xrightarrow{1} 17 \xrightarrow{2} 13 \xrightarrow{3} 5 \xrightarrow{4} 1$ with ECF $\{0, 1, 3, 6, 10\}$.

It turns out that numbers at a given path all share a common prefix: $\{0, 1\}$. Specifically, numbers at a path $p$ are all in the form of $P^{-1}(p) + 2^{|p|}k$ where $|p|$ denotes the length of path, and $k \in \mathbb{N}$. All these numbers share a common prefix among their sequences. The length of the prefix is at most $|p|$.

The proof is simple. Consider an odd number $n$ and $n+2^pk$. The Collatz function has two cases, $3n+1$ and $n/2$. When we look at the first one:

• $n \to 3n+1$ and denote this new number as $n'$.

• $n+2^pk \to 3(n + 2^pk)+1 = 3n+1 + 3\times2^pk = n' + 2^p(3k)$

The other case:

• $n \to n/2$ and denote this new number as $n'$.

• $n + 2^pk \to n/2 + 2^{p-1}k = n' + 2^{p-1}k$

In both cases, the numbers continue be related in a similar form as we start with, that is: $n$ and $n+2^pk$. Only in the division by 2, we must ensure $p$ is large enough so that we can continue dividing by two.

TODO: mention that prefix can be many if you allow "even terminating numbers", but we only allows Odds