How to simplify this summation containing floor

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

Solution 2:

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