4. Any positive integer $n$ can be written in the form $n=2^{a} q$, where $a \geq 0$ and $q$ is odd. We call $q$ the odd part of $n$. Define the sequence $a_{0}, a_{1}, \ldots$, as follows: $a_{0}=2^{2011}-1$ and for $m \geq 0, a_{m+1}$ is the odd part of $3 a_{m}+1$. Find $a_{2011}$.
4. Replace 2011 by any positive odd integer $n$. We first show by induction that $a_{m}=$ $3^{m} 2^{n-m}-1$ for $m=0,1, \ldots, n-1$. This is certainly true for $m=0$. Suppose it's true for some $m1$, the odd part is $3^{m+1} 2^{n-m-1}-1$ which is $a_{m+1}$. Now $a_{n-1}=3^{n-1} 2^{1}-1$. Thus $3 a_{n-1}+1=3^{n} 2-2=2\left(3^{n}-1\right)$. When $n$ is odd, $3^{n} \equiv-1 \quad(\bmod 4)$. Thus $4 \nmid 3^{n}-1$. Hence the odd part of $2\left(3^{n}-1\right)$ is $\frac{3^{n}-1}{2}$ and this is the value of $a_{n}$.