Apologies for the length of my definition. If anyone has suggestions for shortening it, I am glad to update.
Does it follow that for all positive integers $x_1, x_2$ where $x_1 \ne x_2$, there exists $n$ such that $h_n(x_1) \ne h_n(x_2)$? (
Note: See below for the definition $h_n(x)$
My thinking is yes. My reasoning is below. My argument is incomplete. So, I would be very interested if the answer is yes, no, or whether it is an open question.
Let:
$g(x)= \begin{cases} 1,& \text{if } x = 1\\ 3x+1, & \text{otherwise} \end{cases}$
$f^{a,b,c,\dots}(x) = g\left(\dfrac{g\left(\dfrac{g\left(\dfrac{g\left(\dfrac{x}{2^a}\right)}{2^b}\right)}{2^c}\right)}{\vdots}\right)$
$h_n(x) =$ the sequence of numbers generated from applying the rules of the Collatz Conjecture where each number is the maximum power of $2$ that divides the even result generated by adding $1$ after multiplying $3$ to the previous odd result.
Example:
$h_1(3) = 0$ with $f^{0}(3) = 10$
$h_2(3) = 0,1$ with $f^{0,1}(3) = 16$
$h_3(3) = 0,1,4$ with $f^{0,1,4}(3) = 1$
- For integers $x_1 > 0, x_2 > 0, h_n(x_1) = h_n(x_2)$ if and only if each element at the same position in the difference sequences are equal.
Note 1: If $x$ is odd, then $h_1(x) = 0$
Note 2: For all positive $n$, there exists a nonnegative integer $t$ such that $f^{h_n(x)}(x) = 3t + 1$
Note 1: For all nonnegative integers $t,u$, $h_1(2t+1) = h_1(2u+1) = 0$
Note 2: If $h_2(x) = 2,2$ and $h_2(y) = 2,3$, then $h_2(x) \ne h_2(y)$.
Example
$h_4(17) = 0, 2, 3, 4$
$f^{h_4(17)} = f^{0,2,3,4}(17) = g\left(\dfrac{g\left(\dfrac{g\left(\dfrac{g\left(\dfrac{17}{2^0}\right)}{2^2}\right)}{2^3}\right)}{2^4}\right) = 1$
$f^{h_3(17)} = f^{0,2,3}(17) = 5$
$f^{h_5(17)} = f^{0,2,3,4,0} = 1$
Examples:
For $x_1 = 3, x_2 = 4$, $n=1$ and $h_1(3) = 0$ and $h_1(4) = 2$
For $x_1 = 3, x_2 = 5$, $n=2$ and $h_2(3) = 0,1$ and $h_2(5) = $0,4$
It seems to me that it follows that for all positive integers $x_1, x_2$ where $x_1 \ne x_2$, there exists $n$ such that $h_n(x_1) \ne h_n(x_2)$. Here's my thinking for why this is true.
(1) Assume that there are two positive integers $x_1 \ne x_2$ but for all $n > 0, h_n(x_1) = h_n(x_2)$.
(2) Case 1: There exists a minimum $n$ such that $f^{h_n(x_1)}(x_1) = f^{h_n(x_2)}(x_2)$
Define $F^{a,b,c,\dots}(y)$ as the inverse of $f^{a,b,c,\dots}(x)$ so that if $y = f^{a,b,c,\dots}(x)$, then $x = F^{a,b,c,\dots}(y)$
Let $i = f^{h_n(x_1)}(x_1)$
Since the inverse of each function is itself a function, it follows that it is impossible that $x_1 = F^{h_n(x_1)}(i) \ne F^{h_n(x_1)}(i) = F^{h^n(x_2)}(1) = x_2$
(3) Case 2: There is never a case where $f^{h_n(x_1)}(x_1) = f^{h_n(x_2)}(x_2)$ even while for all $n$, $h_n(x_1) = h_n(x_2)$
- Let $a_0 = x_1, b_0 = x_2$
- Define $c_i, d_j$ such that: $a_i = 2a_{i+1} + c_{i+1}$ and $b_j = 2b_{j+1} + d_{j+1}$ where each $c_i, d_j \in \{0,1\}$
- Since $a_0 \ne b_0$, there exists $n$ where $c_n \ne d_n$.
- Let $m$ be the first such time so that $c_m \ne d_m$ but $c_{m-1} = d_{m-1}$
- To complete the argument, I need to show that since $m$ exists, $h_m(x_1) \ne h_m(x_2)$. If I can figure this out, I will update.
Edit: I have made an attempt to complete case 2. It is not complete but I think that the argument is valid if I can add a lemma.
Your attempt at proving case $2$ basically involves checking the lowest binary digits of $x_1$ and $x_2$. However, I don't see any way offhand to algebraically use your method with $h_m(x_1)$ due to the $3x + 1$ operation after removing the powers of $2$ at each step also affects the larger binary digits.
Instead, Collag3n's question comment, i.e.,
is correct. I'll show why this is true and use it below to answer your case $2$, including that the lowest $H$ bits of $x_1$ and $x_2$ must be the same, which is similar to what you were trying to do.
For notational convenience, have $p_j$ be the maximum power of $2$ at each step (so it'll be the $j$'th element of $h_n(x)$), with $y_{j}$ being the odd integer result after dividing by $2^{p_j}$.
For $x_i$, where $i \in \{1, 2\}$, you get
$$x_i = 2^{p_1}y_1 \tag{1}\label{eq1A}$$
Next, you have
$$g(y_1) = 3y_1 + 1 = 2^{p_2}y_2 \tag{2}\label{eq2A}$$
Multiply both sides of \eqref{eq1A} by $3$ and substitute \eqref{eq2A} to get
$$\begin{equation}\begin{aligned} 3x_i & = 2^{p_1}(3y_1) \\ & = 2^{p_1}(2^{p_2}y_2 - 1) \\ & = 2^{p_1 + p_2}y_2 - 2^{p_1} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Next, you get
$$g(y_2) = 3y_2 + 1 = 2^{p_3}y_3 \tag{4}\label{eq4A}$$
As before, multiplying both sides of \eqref{eq3A} by $3$ and substituting \eqref{eq4A} gives
$$\begin{equation}\begin{aligned} 3^2x_i & = 2^{p_1 + p_2}(3y_2) - 3(2^{p_1}) \\ & = 2^{p_1 + p_2}(2^{p_3}y_3 - 1) - 3(2^{p_1}) \\ & = 2^{p_1 + p_2 + p_3}y_3 - 2^{p_1 + p_2} - 3(2^{p_1}) \end{aligned}\end{equation}\tag{5}\label{eq5A}$$
Repeating the steps of multiplying both sides by $3$ and substituting, the next result becomes
$$3^3x_i = 2^{p_1 + p_2 + p_3 + p_4}y_4 - 2^{p_1 + p_2 + p_3} - 3(2^{p_1 + p_2}) - 3^2(2^{p_1}) \tag{6}\label{eq6A}$$
After $n$ steps, you thus get
$$3^{n-1}x_i = 2^{\sum_{j=1}^{n}p_j}y_{n} - \sum_{k=0}^{n-2}3^{k}2^{\sum_{j=1}^{n-k-1}p_j} \tag{7}\label{eq7A}$$
As suggested in Collag3n's comment, have
$$H = \sum_{j=1}^{n}p_j \tag{8}\label{eq8A}$$
Since $3^{n-1}$ is relatively prime to $2^{H}$, it has a multiplicative inverse (call it $m$) modulo $2^{H}$. Using this, \eqref{eq7A} becomes
$$\begin{equation}\begin{aligned} 3^{n-1}x_i & \equiv - \sum_{k=0}^{n-2}3^{k}2^{\sum_{j=1}^{n-k-1}p_j} \pmod{2^H} \\ x_i & \equiv -m\sum_{k=0}^{n-2}3^{k}2^{\sum_{j=1}^{n-k-1}p_j} \pmod{2^H} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$
The right side doesn't depend on $x_i$ but, instead, just on $n$ and the $p_j$, which are assumed to be the same for $h_n(x_1)$ and $h_n(x_2)$. This means
$$x_1 \equiv x_2 \pmod{2^{H}} \tag{10}\label{eq10A}$$
Apart from possibly $p_1$, each $p_j$ for $j \gt 1$ is positive except for the last one, if any, which is $0$. If $h_n(x_1)$ and $h_n(x_2)$ are equal with both ending at $0$ at the same point, your case $1$ applies as you can then use the inverse function to show $x_1 = x_2$. Otherwise, you have basically an unlimited number of positive elements.
In that case, the sum of those elements, i.e., $H$, must be strictly increasing, so $2^H$ is also strictly increasing. Note \eqref{eq10A} shows the lowest $H$ binary bits of $x_1$ and $x_2$ are the same. No matter how large $x_1$ and $x_2$ are, there's an $n$ such that $2^H$ is larger than both of them, so all of the binary bits must match then. This means \eqref{eq10A} can only be true in that case if $x_1 = x_2$. This shows your case $2$ assumption isn't true, i.e., since $x_1 = x_2$, then $f^{h_n(x_1)}(x_1) = f^{h_n(x_2)}(x_2)$ for all $n$.