
4. Let $l(n)$ denote the the greatest odd divisor of any natural number $n$. Find the sum

$$
l(1)+l(2)+l(3)+\cdots+l\left(2^{2013}\right) .
$$

(Michal Rolínek)


Solution. For each natural $k$, the equalities $l(2 k)=l(k)$ and $l(2 k-1)=2 k-1$ are clearly valid. Thus we can add the values $l(n)$ over groups of numbers $n$ lying always between two consecutive powers of 2 . In this way we will prove by induction the formula

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

for $n=1,2,3, \ldots$ The case $n=1$ is trivial. If $s(n)=4^{n-1}$ pro some $n$, then

$$
\begin{aligned}
s(n+1) & =l\left(2^{n}+1\right)+l\left(2^{n}+2\right)+l\left(2^{n-1}+3\right)+\cdots+l\left(2^{n+1}\right) \\
& =\left[\left(2^{n}+1\right)+\left(2^{n-1}+3\right)+\cdots+\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 have used the fact the number of all odd numbers from $2^{n}+1$ to $2^{n+1}-1$ [including both limits] equals $2^{n-1}$.) The proof of (1) by induction is complete.

Using the formula (1) we compute the requested sum as follows:

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

Remark. It is worth mentioning that the formula $s(n)=4^{n-1}$ is a special case of a more general (and surprising) formula

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

which can be proved itself for each natural number $k$ even without using induction. Indeed, all the $k$ summands on the left-hand side of (2) are obviously numbers of the $k$-element subset $\{1,3,5, \ldots, 2 k-1\}$, and moreover, these summands are pairwise distinct, because the ratio of any two numbers from $\{k+1, k+2, \ldots, 2 k\}$ is not a power of 2. Consequently, the sum in (2) equals the sum $1+3+5+\cdots+(2 k-1)$, which is $k^{2}$ as stated in (2).
