Sum of a decreasing geometric series of integers

Question

I'm trying to calculate the sum of integers that are being divided by two (applying the floor function if necessary): $n\mapsto \lfloor \frac{n}{2}\rfloor$.

Let $S(n)=n+\lfloor\frac{n}{2}\rfloor+\left\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\right\rfloor+\ldots$.

For example, $$ \begin{align*} S(100) &= 100 + 50 + 25 + 12 + 6 + 3 + 1 + 0 +\ldots\\ S(3) &= 3 + 1 + 0 + \ldots\\ S(1000) &= 1000 + 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 + 0 + \ldots\end{align*} $$

I'm trying to find a closed form for $S(n)$, where $n\in \mathbb N$. Any ideas?

[Solution] A lot of great answers. Thanks! Here's my java implementation.

int computeHalvesSum(int n) {
  return 2 * n - Integer.bitCount(n)
}

Answer 1

See OEIS sequence A005187 and references there. Depending on what language you're using, the simplest way to compute it may be as $2n - (\text{sum of binary digits of }n)$.

Answer 2

I don't know if it meets your criteria for an analytic solution, but $$ S(n)\sum_{k=0}^{\lfloor \log_2 n\rfloor} \left\lfloor\frac{n}{2^k}\right\rfloor $$

The calculation of $\log_2$ probably means this is not worth implementing (you added that comment while I was writing my answer).

Answer 3

Let $n$ be the number in question, and $m$ be the number of $1$'s in the binary expansion of $n$. For example, if $n=100_{10}=1100100_2$, so $m=3$.

Then the sum you seek is $$S(n)=2n-m$$

This is not constant time in $n$, but it is $O(\log n)$, which is pretty good. I doubt you'll be able to do any better than that, since just writing down the answer takes $O(\log n)$ time.

Answer 4

Let $f(n)$ be the number of $1$s in the binary representation of $n$. Then $S(n)=2n-f(n)$.

To see this: If there is a $1$ in the $2^k$ place in the binary expansion of $n$, then that $1$ contributes $2^k+2^{k-1}+\cdots+2^1+2^0=2^{k+1}-1$ to $S(n)$.

Each contribution is one less than twice the place value of its $1$. So the total contribution is $2n$ minus the number of $1$s in the binary representation of $n$.