> For the complete documentation index, see [llms.txt](https://erhany96.gitbook.io/collatz-prefixes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://erhany96.gitbook.io/collatz-prefixes/theory/recursive-index-parity-tree.md).

# 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.

<figure><img src="https://3802517783-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FAjRXZRgAp6BWy2lL9W4p%2Fuploads%2FcURZ9JXokrIh8Kc8gAUJ%2Friptree16.png?alt=media&amp;token=cb745090-10ee-41b2-98f9-830fcca28aae" alt=""><figcaption><p>RIPTree(16)</p></figcaption></figure>

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.

{% hint style="info" %}
For instance, if a node has $${1, 2,3, 4}$$, then its left child has $${2, 4}$$ and its right child has $${1, 3}$$.
{% endhint %}

## 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.](https://oeis.org/A036044)

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

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

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

{% hint style="danger" %}
TODO: mention that prefix can be many if you allow "even terminating numbers", but we only allows Odds
{% endhint %}