Let $d(n)$ denote the largest odd integer divides $n$. Calculate the sum $d(1)+d(2)+d(3)+\dots+d(2^{99})$.
Problem
Source:
Tags:
19.01.2013 10:37
Obviously, $d(n)={n\over 2^{\text{ord}_2(n)}}$. For $0\leqslant\text{ord}_2(n)\leqslant 98$, the values of $d(n)$ run over odd numbers between $1$ and $2^{99-\text{ord}_2(n)}-1$, the sum of which is $4^{98-\text{ord}_2(n)}$, and for $\text{ord}_2(n)=99$ we have $d\left(2^{99}\right)=1$. Hence $S=1+\sum_{k=0}^{98}4^{98-k}=1+\sum_{k=0}^{98}4^k=1+{4^{99}-1\over 3}={4^{99}+2\over 3}$
19.01.2013 19:32
xeroxia wrote: Let $d(n)$ denote the largest odd integer divides $n$. Calculate the sum $d(1)+d(2)+d(3)+\dots+d(2^{99})$. Let $S_n=d(1)+d(2)+d(3)+\dots+d(2^{n})$ $=1+3+5+\dots+(2^{n}-1) +d(2)+d(4)+\dots+d(2^n) \\=\left(\frac{2^n-1+1}{2}\right)^2 +S_{n-1} \\=S_0 +\sum_{k=1}^{n} 4^{n-1} \\=1+\frac{1-4^n}{1-4} \\=\frac{4^n+2}{3} $ which of course gives the same answer for $S_{99}$ that Farenhajt already gave.