Start with a number equal to $-1$ modulo $2^n$. Then, after one step, the number is $\frac{3(-1)+1}{2}=-1$ modulo $\frac{2^n}{2}=2^{n-1}$, so inductively it will increase $n$ steps.
user35593
- 2.3k
- 12
- 19