sum of integral part of n/k

Question

Is there any direct formula or algorithm better than the brute force (O(n) algorithm by iterating from 1 to n) way to calculate the sum

\begin{equation} S = \sum\limits_{i=1}^n [{\frac{n}{i}}] \end{equation}

where [x] denotes the integral part of x?

I tried out calculating the sum by considering i's that are factors of n. But that does not seem to give the correct answer. Any help in any form is welcomed.

Please point out the mistakes in tags and formatting of the question too, since I am a beginner here.

Answer 1

For questions like this searching for the first few terms in OEIS might help 3, 5, 8, 10, 14, 16, 20, 23, 27, 29, 35, 37, 41

This is A006218.

There are a lot of references and bounds for the sum.

In particular there is a formula $O(\sqrt{n})$:

a(n)=2*sum(i=1, floor(sqrt(n)), floor(n/i))-floor(sqrt(n))^2 - Benoit Cloitre

$$ a(n) = (2 \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \lfloor n/i \rfloor) - {\lfloor \sqrt{n} \rfloor}^2 $$

Another comment:

The Polymath project (see the Tao-Croot-Helfgott link) sketches an algorithm for computing a(n) in essentially cube root time, see section 2.1