Sum of floor of ratios

Question

I need to compute, in a program at work, the sum, for $k = 2$ to $n-1$, of the floors of the ratios: $\frac{n}{k}$.

Since n is a large integer in my case I would need a "closed form" formula for this sum, or any other way (any algorithm) which can allow me to skip completely the $n-2$ operations (and any function of n, unless it is a logarithm power or something slower than that). Ideally, I would like to compute the formula without any looping.

Do you have a closed formula or suggestions ?

(Although I need an "exact" result, if there are asymptotic expressions I would also be interested in taking a look at them, as in my case n is large)

Answer 1

Asymptotically, as $n$ becomes large, first note that $$\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor<\sum_{k=2}^{n-1} \frac nk<\int_1^{n-1}\frac nx\,dx=n\ln(n-1).$$ Also $$n+\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor>\sum_{k=2}^{n-1} \frac nk>\int_2^{n}\frac nx\,dx=n(\ln n-\ln2),$$ and in summary, $$n(\ln n-1-\ln2)<\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor<n\ln n.$$

Answer 2

Hint: you can get to $\sqrt n$ execution by noting that when $k$ is large (how large?), $\lfloor \frac nk \rfloor = 1$. Compute ranges of $k$ for which the floor is constant. On the other hand, when $k$ is small it is easy to compute the sum exactly-play with $k=2$ and $k=3$ by hand and you should be able to find the pattern. These two approaches meet where $k \approx \sqrt n$