# Sum of floor of ratios

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)

• Just to be clear, the n is the same throughout the sum and the k is changing? Ie the sum is $\sum_{k=2}^{n-1}\lfloor \frac{n}{k} \rfloor$? – DavidButlerUofA Aug 12 '14 at 16:40
• That is right David. – Pam Aug 12 '14 at 16:48
• If you sum from $1$ to $n$ instead of $2$ to $n-1$, it will be equal to the divisor summatory function which can be computed in $O(\sqrt{n})$ time. $$D(n) = \sum_{k=1}^n \lfloor \frac{n}{k}\rfloor = 2\sum_{k=1}^u \lfloor \frac{n}{k}\rfloor - u^2\quad\text{ where }\quad u = \lfloor\sqrt{n}\rfloor$$ and for large $n$, we know $$D(n) = n\log n + n(2\gamma -1) + O(\sqrt{n})$$ – achille hui Aug 12 '14 at 17:05
• Thank you Achille. "divisor summatory function", I see, very nice. – Pam Aug 12 '14 at 17:26
• In this answer, it is shown that $$\sum_{k=2}^{n-1}\left\lfloor\frac nk\right\rfloor =n\log(n)-2(1-\gamma)n+O(\sqrt{n})$$ where the big-O term is bounded by $3\sqrt{n}$ – robjohn Jul 3 '15 at 2:44

## 2 Answers

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

• That's nice. A bit large as interval to be very useful in the application though. Could we at least get a bounded-width (say, size of interval not depending on $n$) interval containing the exact result ? – Pam Aug 12 '14 at 16:26
• Sorry, I think getting a formula with much sharper bounds is going to take a lot more work. – Harald Hanche-Olsen Aug 12 '14 at 17:17
• Considering that this seems to be a known difficult problem, as achille (comment above) just pointed out, you did pretty well :-) – Pam Aug 12 '14 at 17:36
• Well, I am accepting this "answer" for now. If there are developments feel free to update and add new answers: I will continue following the topic. Thank you very much Ross and Harald and David and Achille – Pam Aug 20 '14 at 16:45

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$

• My thought exactly. For a bit more detail, note that $\lfloor n/k\rfloor=j$ is equivalent to $n/(j+1)<k\le n/j$, and the number of such $k$ is easily counted (be careful though; it matters whether $j+1\mid n$ or not). The length of the indicated interval is $n/(j(j+1))$, so this will be good for $j<\sqrt{n}$, with only the cases $k<\sqrt{n}$ remaining. (The latter two inequalities are approximate; some care is needed to make it exact.) – Harald Hanche-Olsen Aug 12 '14 at 15:23
• Thanks a lot. I would need either an "exact" result for the sum (that would be absolutely great) or something computable in a relatively "small" number of steps, where "small" means for instance log(n) steps or so. Do you think this is possible ? – Pam Aug 12 '14 at 15:30
• One should be careful saying something can't be done, but I have a hard time seeing how you could improve on $O(\sqrt{n})$ for computing an exact result. – Harald Hanche-Olsen Aug 12 '14 at 15:42