Iterative Method

With the theory described so far, we can construct alternative methods to find the sequence of a number.

Path Extension in RIPTree

We have shown that numbers at the same path have a common prefix, but the length of this was at most the length of path. We have also mentioned that appending 1s to some path $p$ does not change the result of $P^{-1}(p)$. Increasing the length of path means that we can analyze our number within a larger PIPTree, which may allow us to find a prefix so large that it is actually the sequence itself.

Traversing the PIPTree

It is simple to find the prefix of a number using PIPTree. To be more specific, we are finding the prefix of a number $n$ for some path $p$ such that $P^{-1}(p) = n$. As mentioned before, a larger $p$ allows us to find the sequence faster.

For a given path $p$ and some number $n = P^{-1}(p)$, we do as follows:

1. Construct a PIPTree for $|p|$. We start at the root node with prefix $\{|p|-1\}$ and number $2^{|p|-1}$

2. We need to find the directions from the node that has $n$ to the root. This can be done easily, described in a later subsection

3. Find the next node with respect to the directions

4. Calculate the nature of current node, and update the prefix with respect to the nature to move on to the next node

5. Repeat these steps until you reach the node with $n$

6. Denote the final computed prefix as $\rho$. Consider the bijective map of $\rho$ as $m$, if $\beta(n, m) = 1$ then stop. Otherwise, repeat the entire process for number $\circ(n, m)$. While repeating, the computed prefix should be noted down.

TODO: Give a better pseudo-algorithm