2. (BUL 3) Let $n$ be a positive integer. Find the number of odd coefficients of the polynomial  
$$ u_{n}(x)=\left(x^{2}+x+1\right)^{n} $$
2. For polynomials $f(x), g(x)$ with integer coefficients, we use the notation $f(x) \sim g(x)$ if all the coefficients of $f-g$ are even. Let $n=2^{s}$. It is immediately shown by induction that $\left(x^{2}+x+1\right)^{2^{s}} \sim x^{2^{s+1}}+x^{2^{s}}+1$, and the required number for $n=2^{s}$ is 3. Let $n=2^{s}-1$. If $s$ is odd, then $n \equiv 1(\bmod 3)$, while for $s$ even, $n \equiv 0$ $(\bmod 3)$. Consider the polynomial 
$$ R_{s}(x)= \begin{cases}(x+1)\left(x^{2 n-1}+x^{2 n-4}+\cdots+x^{n+3}\right)+x^{n+1} & \\ +x^{n}+x^{n-1}+(x+1)\left(x^{n-4}+x^{n-7}+\cdots+1\right), & 2 \nmid s \\ (x+1)\left(x^{2 n-1}+x^{2 n-4}+\cdots+x^{n+2}\right)+x^{n} & \\ +(x+1)\left(x^{n-3}+x^{n-6}+\cdots+1\right), & 2 \mid s\end{cases} $$
It is easily checked that $\left(x^{2}+x+1\right) R_{s}(x) \sim x^{2^{s+1}}+x^{2^{s}}+1 \sim\left(x^{2}+x+1\right)^{2^{s}}$, so that $R_{s}(x) \sim\left(x^{2}+x+1\right)^{2^{s}-1}$. In this case, the number of odd coefficients is $\left(2^{s+2}-(-1)^{s}\right) / 3$. Now we pass to the general case. Let the number $n$ be represented in the binary system as 
$$ n=\underbrace{11 \ldots 1}_{a_{k}} \underbrace{00 \ldots 0}_{b_{k}} \underbrace{11 \ldots 1}_{a_{k-1}} \underbrace{00 \ldots 0}_{b_{k-1}} \cdots \underbrace{11 \ldots 1}_{a_{1}} \underbrace{00 \ldots 0}_{b_{1}} $$
$b_{i}>0(i>1), b_{1} \geq 0$, and $a_{i}>0$. Then $n=\sum_{i=1}^{k} 2^{s_{i}}\left(2^{a_{i}}-1\right)$, where $s_{i}=b_{1}+a_{1}+b_{2}+a_{2}+\cdots+b_{i}$, and hence 
$$ u_{n}(x)=\left(x^{2}+x+1\right)^{n}=\prod_{i=1}^{k}\left(x^{2}+x+1\right)^{2^{s_{i}}\left(2^{a_{i}}-1\right)} \sim \prod_{i=1}^{k} R_{a_{i}}\left(x^{2^{s_{i}}}\right) $$
Let $R_{a_{i}}\left(x^{2^{s_{i}}}\right) \sim x^{r_{i, 1}}+\cdots+x^{r_{i, d_{i}}}$; clearly $r_{i, j}$ is divisible by $2^{s_{i}}$ and $r_{i, j} \leq 2^{s_{i}+1}\left(2^{a_{i}}-1\right)<2^{s_{i+1}}$, so that for any $j, r_{i, j}$ can have nonzero binary digits only in some position $t, s_{i} \leq t \leq s_{i+1}-1$. Therefore, in 
$$ \prod_{i=1}^{k} R_{a_{i}}\left(x^{2^{s_{i}}}\right) \sim \prod_{i=1}^{k}\left(x^{r_{i, 1}}+\cdots+x^{r_{i, d_{i}}}\right)=\sum_{i=1}^{k} \sum_{p_{i}=1}^{d_{i}} x^{r_{1, p_{1}}+r_{2, p_{2}}+\cdots+r_{k, p_{k}}} $$
all the exponents $r_{1, p_{1}}+r_{2, p_{2}}+\cdots+r_{k, p_{k}}$ are different, so that the number of odd coefficients in $u_{n}(x)$ is 
$$ \prod_{i=1}^{k} d_{i}=\prod_{i=1}^{k} \frac{2^{a_{i}+2}-(-1)^{a_{i}}}{3} $$