For any composition sequence $s$ of maps $h(X)=X/2, \ f(X)=(3X + 1)/2$, there exists an integer $X$ such that its Collatz sequence contains $s$

Question

Let $h(X) = X/2$, and $f(X) = (3X + 1)/2$. Then clearly every iteration $g^i(X), X \in \Bbb{Z}$ the Collatz mapping $$g(X) = \begin{cases} X/2, \ X=0\pmod 2\\ \dfrac{3X + 1}{2}, \ X = 1\pmod 2 \end{cases}$$ can be modelled by compositions of $f, h$.

For example, $g^7(3) = 1 = hhhff(3)$ where $g(X) = f(X)$ for odd numbers and $g(X) = h(X)$ for even numbers.

Under iterations of $g$, each number $X \in \Bbb{Z}$ induces a unique composition of $f$ and $h$ functions. This should be clear because a number is either even or odd but not both, so at each stage in an iteration there is one and only one function ($f$ or $h$) to apply.

Conjecture. For any sequence $s \in \{f,h\}^*$ (Kleene closure under $\circ$) there exists an integer $X$ such that $g^i(X) = s(X)$ for some $i \geq 0$.

Can we prove this or is it just as difficult as Collatz?

---

Clearly we have that it's true for the sublanguage $\{h\}^*$ since we can take $g^n(2^n) = h^n(X)$ for all $n \geq 0$.

Clearly we have that it's true for the sublanguage $\{h\}^*$ since we can take $g^n(2^n) = h^n(X)$ for all $n \geq 0$. It's also true for $f\{h\}^*$ since $X = 2^n O$ works, where $O$ is an odd number.

And it's true for $\{h\}^* f$ since $3O + 1 = 2^ny$ has a solution if and only if $30 + 1 = 0 \pmod 2^n \iff O = -3^{-1} \pmod 2^n$. So in fact we've proven an infinitude of solutions namely: $-3^{-1} + 2^n\Bbb{Z}$ for any $h^n f \in \{h\}^* f$.

Let these two proofs comprise a base case for induction on the number of $f$'s appearing in $s$.

Answer 1

To be honest, we can prove it by induction.

Suppose for a $m$-length sequence $f,h$ there exists a modulo $M$ such that for any starting number $k=2^mt+M$, the first $m$ step of $g$ is exactly that sequence. For $m=1$ it is trivial, since we can choose $M=0$ if the sequence if $h$, and $M=1$ if the sequence is $f$.

Suppose this is true for $m$, we now prove it for $m+1$. Let the sequence be $a_1a_2\dots a_ma_{m+1}$ where each $a_i\in \{h,f\}$. By induction, there exist an $M'$ such that for any starting number $k=2^mt+M$, the first $m$ step of $g$ is exactly that sequence $a_2\dots a_ma_{m+1}$. So to achieve the new sequence, we need to select whether $M\equiv M'\mod 2^{m+1}$ or $M\equiv M'+2^m\mod 2^{m+1}$. Notice that after $a_2\dots a_ma_{m+1}$, the function is $\frac{Ax+B}{2^m}$ where $A$ is $3$ to the number of $f$ in the sequence $a_2\dots a_ma_{m+1}$ (thus $A$ is odd) and $B$ is some integer. So when plug in $k$, we have $a_2\dots a_ma_{m+1}(k)=\frac{Ak+B}{2^m}=\frac{A(2^mt+M)+B}{2^m}=At+\frac{AM+B}{2^m}\equiv t+\frac{AM+B}{2^m}\mod 2$. So we can choose $t$ and $\frac{AM+B}{2^m}$ be the same parity if $a_1$ is $h$, and choose $t$ and $\frac{AM+B}{2^m}$ be the differentparity if $a_1$ is $f$. Therefore we can choose the new $M$ to be $M'$ if we choose $t$ to be even, or $M'+2^t$ if we choose $t$ to be odd. Hence we can finish the proof.

Answer 2

It's true by the above base cases for all $s = f h^n, n \geq 0$. Now suppose that $s$ has a count of $k$ total $f$'s in it, and that it begins with an $f$ (on the left). Then

$$ fh^{n_1}(2^{n_1} O_1) = f(O_1) = 3O_1 + 1 = 2^{n_2}O_2, \dots \\ \text{Clearly, } \gcd(O_1, O_2) = 1 \text{ should } O_2 \text{ exist }. \\ \ \\ 3 O_1 + 1 = 0 \pmod{2^{n_2}O_2} \\ 3 O_2 + 1 = 0 \pmod{2^{n_3}O_3} \\ \vdots \\ 3 O_{k-1} + 1= 0 \pmod{2^{n_k}O_k} $$

Solving for the $O_i$ given the $n_i$ is what it amounts to. Seems hard, right? Actually, work from the bottom up: solve $3 O_{k-1} + 1 = 0 \pmod{2^{n_k} O_k}$. First, pick any odd number $O_k \in 2\Bbb{Z} + 1$ such that $3 \nmid O_k$. Then solve for $O_{k-1} = -3^{-1} \pmod {2^{n_k} O_k}$. Repeat the process until you've solved for $O_1$. And we're done.

The only case I have remaining is that of $h^n f\{f, h\}^*$ i.e. for $n \geq 1$. For that case, simply take $X = 2^{n_{k+1}} O_k$ from the previous proof.

This started as an attempt, but kind of ended in an answer.