0

Here's the summation: $$ S = \sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor $$

It can also be written as $$ S = \sum_{i=1}^{n}\left\lfloor\frac{n- (n \mod i)}{i}\right\rfloor $$

The answer will always be an integer, but I can't figure out how to solve it. I tried separating them and taking n common, then solving $ \sum_{i=1}^{n}\frac{1}{i} $, but there's no way you can get the exact integral answer that way.

Any help will be appreciated.

Rushil Paul
  • 242

2 Answers2

1

This is at least the third time recently that this sum has come up in one of its various forms. It isn't possible to get an exact simple formula for the sum - though it is possible to get a simple approximation. Note that $\left\lfloor \frac ni \right\rfloor$ counts the number of multiples of $i$ which are greater than zero and less than or equal to $n$.

This is the same as counting the number of integer points (a,b) which are on or below the hyperbola $xy=n$ for $a, b \gt 0$.

Summing these terms is the same as the taking the sum of the divisor function (which also counts the points in relation to the hyperbola), which is known to be $$n\log n +(2\gamma-1)n+O(\sqrt n)$$ There is a proof, for example, In Hardy and Wright's "Introduction to the Theory of Numbers". In fact the error term can be improved and getting a good estimate is known as the Dirichlet Divisor Problem.

See this question (which looks quite different at first glance) for some further comments and links.

Community
  • 1
Mark Bennet
  • 100,194
  • As soon as I posted the question, I found those 2 questions! Well I went through the answers, but the answers I get programmatically will be an approximation. I'm not sure whether my answer will always be correct. – Rushil Paul Sep 07 '13 at 14:26
  • Btw, this question is located here: http://www.codechef.com/SEPT13/problems/COOLGUYS – Rushil Paul Sep 07 '13 at 14:26
1

Since you want to compute the exact value of the sum for some ($\leqslant 1000$) not too small, but also not very large $n$ ($\leqslant 10^9$) in constrained time, here's a hint:

$$\left\lfloor \frac{n}{i}\right\rfloor = k \iff k \leqslant \frac{n}{i} < k+1 \iff \frac{n}{k+1} < i \leqslant \frac{n}{k},$$

so there are $\left\lfloor\dfrac{n}{k}\right\rfloor - \left\lfloor \dfrac{n}{k+1}\right\rfloor$ terms with value $k$.

Let $r = \lfloor\sqrt{n}\rfloor$. Then

$$\sum_{i=1}^n \left\lfloor \frac{n}{i}\right\rfloor = \sum_{i=1}^r \left\lfloor \frac{n}{i}\right\rfloor + \sum_{k=1}^{r-1}k\cdot\left(\left\lfloor\frac{n}{k}\right\rfloor - \left\lfloor\frac{n}{k+1}\right\rfloor\right) + r\cdot\left(\left\lfloor\frac{n}{r}\right\rfloor - r\right).$$

Daniel Fischer
  • 206,697