For the sequence \begin{align} a_0&\in\mathbb{N}+1=\{1,2,3,\dots\}\\ a_{k+1}&= \left\{ \begin{array}{rl} a_k \div 2 & \quad2\mid a_k \\ 3a_k+1 & \quad2\nmid a_k \end{array} \right. \end{align} the Collatz conjecture states that \begin{equation} \forall\,a_0\,\exists\,k\text{ such that } a_k=1 \end{equation}

In base 2, the process can be rephrased as repeatedly

Removing trailing 0s (removes factors of 2 until odd)
Appending 1 to the end of the number (\(=2a_k+1\))
Adding the result to the previous number (\(=3a_k+1\))

For example (via Wikipedia ), \(7=111_2\)

         111         7
        1111
       10110        11
      10111
     100010         17
    100011
    110100          13
   11011
  101000             5
 1011
10000                1

The process can be rephrased in base 3 with a 1 (carry) bit left-to-right state-machine.

Initially, the carry bit is off, so \(0\to0\) and \(2\to1\)
With the carry bit off, \(1\to0\), flipping the carry bit on
With the carry bit on, \(1\to2\), flipping the carry bit off
With the carry bit on, \(0\to1\) and \(2\to2\)
If the number ends with the carry bit on, append 2

In base 3, the parity of the number is equal to the parity of the popcount for 1s digits. The number is only divided by 2 if it is even, meaning that the carry is the same going left-to-right as right-to-left. If the number ends with the carry bit on, the previous step was odd, meaning a 1 is missing (to get \(3a_k+1\)), which gets converted to a 2 to end the carry.

Using = ₃

21              7
102            11
0122           17
 0222          26
  111          13
  0202         20
   101         10
   012          5
    022         8
     11         4
     02         2
      1         1