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.
Best Answer
For the initial sum see sequence A006218 from OEIS and the Wikipedia page about the 'Divisor summatory function'.
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...)
Some other references :