4. Let l(n) denote the greatest odd divisor of the number n. Determine the value of the sum

$$
l(1)+l(2)+l(3)+\ldots+l\left(2^{2013}\right) .
$$
SOLUTION. It is evident that for every natural number $k$ the equalities $l(2 k)=l(k)$ and $l(2 k-1)=2 k-1$ hold. Thanks to them, the values of $l(n)$ can be summed in groups of numbers $n$ lying between two consecutive powers of the number 2, precisely determining the sums

$$
s(n)=l\left(2^{n-1}+1\right)+l\left(2^{n-1}+2\right)+l\left(2^{n-1}+3\right)+\ldots+l\left(2^{n}\right)
$$

successively for individual $n=1,2,3, \ldots$ For clarity, let us first outline the procedure for determining a specific sum

$$
s(4)=l(9)+l(10)+l(11)+l(12)+l(13)+l(14)+l(15)+l(16) \text {. }
$$

The contribution of its summands $l(2 k-1)$ is equal to

$$
l(9)+l(11)+l(13)+l(15)=9+11+13+15=\frac{4}{2} \cdot(9+15)=48
$$

(we have indicated the use of the formula for the sum of several terms of an arithmetic sequence), while the contribution of the summands $l(2 k)$ has the value

$$
l(10)+l(12)+l(14)+l(16)=l(5)+l(6)+l(7)+l(8) \text {. }
$$

However, this is the "previous" sum $s(3)$, which we could have already determined from the sum $s(1)=1$ by a similar, now more concisely written procedure:

$$
s(3)=l(5)+l(6)+l(7)+l(8)=5+7+s(2)=12+3+s(1)=15+1=16 \text {. }
$$

Now we can easily calculate $s(4)=48+s(3)=64$.

The performed calculation leads us to the hypothesis that for every $n$ it holds that $s(n)=4^{n-1}$. We will prove this by mathematical induction. If $s(n)=4^{n-1}$ holds for a certain $n$ (as is the case for $n=1,2,3$), then for the sum $s(n+1)$, according to our procedure, we get

$$
\begin{aligned}
s(n+1) & =l\left(2^{n}+1\right)+l\left(2^{n}+2\right)+l\left(2^{n-1}+3\right)+\ldots+l\left(2^{n+1}\right)= \\
& =\left[\left(2^{n}+1\right)+\left(2^{n-1}+3\right)+\ldots+\left(2^{n+1}-1\right)\right]+s(n)= \\
& =\frac{2^{n-1}}{2}\left(2^{n}+1+2^{n+1}-1\right)+4^{n-1}=2^{n-2} \cdot 3 \cdot 2^{n}+4^{n-1}=4^{n} .
\end{aligned}
$$

(We used the fact that the number of odd numbers from $2^{n}+1$ to $2^{n+1}-1$ inclusive is equal to $2^{n-1}$.) The proof by induction is complete.

According to the proven formula $s(n)=4^{n-1}$, for the sum from the problem statement, we have

$$
\begin{array}{r}
l(1)+l(2)+l(3)+\ldots+l\left(2^{2013}\right)=l(1)+s(2)+s(3)+\ldots+s(2013)= \\
\quad=1+1+4+4^{2}+4^{3}+\ldots+4^{2012}=1+\frac{4^{2013}-1}{3}=\frac{4^{2013}+2}{3} .
\end{array}
$$

Note. It is certainly worth noting that the formula $s(n)=4^{n-1}$ from the given solution is a special case of a quite surprising relationship

$$
l(k+1)+l(k+2)+l(k+3)+\ldots+l(2 k)=k^{2},
$$

which can be proven for every natural number $k$ without using induction by the following elegant argument: All $k$ summands on the left side (1) are clearly numbers from the $k$-element set $\{1,3,5, \ldots, 2 k-1\}$ and are pairwise distinct, because the ratio of any two numbers from the set of corresponding arguments $\{k+1, k+2, \ldots, 2 k\}$ is not a power of 2. Therefore, (up to the order of the summands) on the left side (1) is the sum $1+3+5+\ldots+(2 k-1)$, which indeed has the value $k^{2}$.

GUIDING AND SUPPLEMENTARY PROBLEMS: