1
$\begingroup$

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)
}
$\endgroup$
  • $\begingroup$ What exactly do you mean by analytic solution of S(n)? Because this could easily be expressed using sigma notation and a recursive function, but I don't think that is what you are after. $\endgroup$ – Dasherman Dec 29 '14 at 18:38
  • $\begingroup$ Yeah "analytic solution" might not be the right translation for what I have in mind. Let's say that I would like to be able to implement an algorithm that compute the solution in constant time. Is it more clear? $\endgroup$ – user1534422 Dec 29 '14 at 18:45
2
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It takes $O(\log(n))$ simply to scan the digits of $n$, so you can't do better than that. $\endgroup$ – Robert Israel Dec 29 '14 at 18:56
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.