Largest Odd Divisor Sum Help For a positive integer $n$, let $d(n)$ be the largest odd divisor of $n$. Find the last three digits of the sum $d(1)+d(2)+d(3)+⋯+d(2^{99}).$
I have that the odd terms sum to $2^{196}$ but am stuck on the even terms. Can someone provide a hint or a solution? Thanks.
 A: Notice that
$$d(2n)=d(n)$$
since $2$ cannot be an odd divisor. Now let us separate your sum into even and odd terms:
$$\sum_{n=1}^{2^{99}} d(n)$$
$$=\sum_{n=1}^{2^{98}} d(2n)+\sum_{n=1}^{2^{98}} d(2n-1)$$
and now, since $d(2n)=d(n)$, we have
$$=\sum_{n=1}^{2^{98}} d(n)+\sum_{n=1}^{2^{98}} d(2n-1)$$
Now we can split it up again:
$$=\sum_{n=1}^{2^{97}} d(2n)+\sum_{n=1}^{2^{97}} d(2n-1)+\sum_{n=1}^{2^{98}} d(2n-1)$$
or
$$=\sum_{n=1}^{2^{97}} d(n)+\sum_{n=1}^{2^{97}} d(2n-1)+\sum_{n=1}^{2^{98}} d(2n-1)$$
If we continue this process, we end up with
$$=1+\sum_{k=0}^{98}\sum_{n=1}^{2^k}d(2n-1)$$
And since you seem to know how to calculate the sum of odd terms, this sum should be manageable for you.
EDIT: I had a bit of a brain fart and didn't realize that 
$$d(2n-1)=2n-1$$
so now we have
$$=1+\sum_{k=0}^{98}\sum_{n=1}^{2^k} 2n-1$$
and since the sum of the first $a$ odd numbers is $a^2$,
$$=1+\sum_{k=0}^{98} (2^k)^2$$
$$=1+\sum_{k=0}^{98} 4^{k}$$
and this is just a geometric sequence that, using the formula
$$\sum_{k=0}^n a^k=\frac{1-a^{n+1}}{1-a}$$
sums to
$$=1+\frac{4^{99}-1}{3}$$
$$=\color{green}{\frac{4^{99}+2}{3}}$$
Can you find the last three digits of this?
A: here's how I'd do it ( i'm stupid like that): 


*

*partial sums of the odd numbers up to n = squares

*even numbers are 2*x if x is odd then repeat step one using x.

*repeat 1 and 2 until all steps are done you will get something like


$$\sum_{i=1}^n d(i)=\sum_{i=0}^{\lfloor\log_2(n)\rfloor}\sum_{j=0}^{\lfloor {n\over2^{i+1}}\rfloor}(2j+1)$$
A: There's already a correct posted answer. My answer shows another solution.
Hint: for all $n\ge 1$, $n\in\mathbb Z$, $$d(n)=\frac{n}{2^{\upsilon_2(n)}},$$
where $\upsilon_2(n)$ means the exponent of the highest power of $2$ that divides $n$.
$$\sum_{i=1}^{2^{99}} d(i)=\sum_{i=1}^{2^{99}} \frac{i}{2^{\upsilon_2(i)}}=$$
$$=\sum_{i|\upsilon_2(i)=0}d(i)+\sum_{i|\upsilon_2(i)=1}d(i)+\cdots+$$
$$+\sum_{i|\upsilon_2(i)=99}d(i)=$$
You can notice that for all $0\le k\le 98$, $k\in\mathbb Z$ we have
$2^k(2(2^{98-k}-1)+1)=2^{99}-2^k<2^{99}$,
$2^k(2(2^{98-k})+1)=2^{99}+2^k>2^{99}$.
$$=\frac{1}{2^0}\left(\sum_{i=0}^{2^{98}-1}(2^0(2i+1))\right)+$$
$$+\frac{1}{2^1}\left(\sum_{i=0}^{2^{97}-1}(2^1(2i+1))\right)+$$
$$+\frac{1}{2^2}\left(\sum_{i=0}^{2^{96}-1}(2^2(2i+1))\right)+\cdots+$$
$$+\frac{1}{2^{98}}\left(\sum_{i=0}^{2^0-1}(2^{98}(2i+1))\right)+\frac{2^{99}}{2^{99}}=$$
$$=\sum_{j=0}^{98} \left(\sum_{i=0}^{2^j-1}(2i+1)\right)+1=$$
$$=\sum_{j=0}^{98}\left(2\sum_{i=0}^{2^j-1}(i) + \sum_{i=0}^{2^j-1}(1)\right)+1=$$
$$=\sum_{j=0}^{98}\left(2\cdot \frac{(2^j-1)(2^j)}{2}+2^j\right)+1=$$
$$=\sum_{j=0}^{98}((2^j-1)(2^j)+2^j)+1=$$
$$=\sum_{j=0}^{98}(4^j-2^j+2^j)+1=$$
$$=\sum_{j=0}^{98} (4^j)+1$$
Use the geometric progression sum formula.
As WolframAlpha suggests, the answer is $782$.
The answer is the same if you use the method given by another answerer. http://www.wolframalpha.com/input/?i=((4%5E99%2B2)%2F3)+mod+1000
