# Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize that there is probably not a closed form, but is there an efficient way to calculate the following expression?

$$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$

I've noticed $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor = \left\lfloor\frac{1}{2}\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} \left\lfloor\frac{n}{k}\right\rfloor\right\rfloor + \sum_{k=1,\ odd(k)}^n \left\lfloor \frac{n}{k}\right\rfloor$$

But I can't see an easy way to let the second term enter in a recursion.

Richard Sladkey's paper 'A Successive Approximation Algorithm for Computing the Divisor Summatory Function' proposes evolutions of the classical : $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor=2\sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \left\lfloor \frac{n}{k}\right\rfloor-\left\lfloor\sqrt{n}\right\rfloor^2$$ (perhaps that making this recursive...)
In addition to Raymond's neat formula, I found the following less neat version. It is based on the observation that after around $\sqrt n$ terms, we start seeing a lot of repeated values. By looking at how many solutions there are to $\lfloor\frac{n}{k}\rfloor=a$ we can get an expression like:
$$\underbrace{\sum_{k=1}^{\lfloor\frac{n}{\lfloor\sqrt n\rfloor-1}\rfloor}\lfloor\frac{n}{k}\rfloor}_\text{Direct calculation of sparse values} + \underbrace{\sum_{a=1}^{\lfloor\sqrt n\rfloor}a(\lfloor\frac{n}{a}\rfloor-\lfloor\frac{n}{a+1}\rfloor)}_\text{Grouped calculation of dense values}$$
This is useful if you need to sum something more complex like $\sum_{k=1}^nk^m\lfloor\frac{n}{k}\rfloor$