Let $n$ be a positive integer. How many polynomials $P$ with coefficients in the set $\{0,1,2,3\}$ are there such that $P(2)=n$?
The natural idea is to relate $P(2)$ to binary expansions. Let $P$ be a polynomial with coefficients in $\{0,1,2,3\}$ of degree $m$, which we write as $P=\sum_{i=0}^{m} a_{i} X^{i}$. Now, for all $i$, write $a_{i}=2 b_{i}+c_{i}$, with $b_{i}$ and $c_{i}$ in $\{0,1\}$, the binary decomposition of $a_{i}$. Thus, we have

$$
P(2)=2 \sum_{i=0}^{m} b_{i} 2^{i}+\sum_{i=0}^{m} c_{i} 2^{i}
$$

Therefore, for $P(2)$ to be equal to $n$, it is necessary that $\overline{a_{n} a_{n-1} a_{0}}$ be the binary representation of $n-2 \sum_{i=0}^{m} b_{i} 2^{i}$, and for this to be possible, $\overline{b_{n} b_{n-1} b_{0}}$ must belong to $\{0,1, \ldots\lfloor n / 2\rfloor\}$. The set of polynomials we are looking for is thus in bijection with $\{0,1, \ldots\lfloor n / 2\rfloor\}$, and the desired quantity is $\lfloor n / 2\rfloor+1$.