2
$\begingroup$

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)

$\endgroup$
5
  • 1
    $\begingroup$ 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$? $\endgroup$ – DavidButlerUofA Aug 12 '14 at 16:40
  • $\begingroup$ That is right David. $\endgroup$ – Pam Aug 12 '14 at 16:48
  • 2
    $\begingroup$ 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})$$ $\endgroup$ – achille hui Aug 12 '14 at 17:05
  • $\begingroup$ Thank you Achille. "divisor summatory function", I see, very nice. $\endgroup$ – Pam Aug 12 '14 at 17:26
  • $\begingroup$ 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}$ $\endgroup$ – robjohn Jul 3 '15 at 2:44
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 ? $\endgroup$ – Pam Aug 12 '14 at 16:26
  • $\begingroup$ Sorry, I think getting a formula with much sharper bounds is going to take a lot more work. $\endgroup$ – Harald Hanche-Olsen Aug 12 '14 at 17:17
  • $\begingroup$ Considering that this seems to be a known difficult problem, as achille (comment above) just pointed out, you did pretty well :-) $\endgroup$ – Pam Aug 12 '14 at 17:36
  • $\begingroup$ 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 $\endgroup$ – Pam Aug 20 '14 at 16:45
3
$\begingroup$

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$

$\endgroup$
3
  • 1
    $\begingroup$ 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.) $\endgroup$ – Harald Hanche-Olsen Aug 12 '14 at 15:23
  • $\begingroup$ 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 ? $\endgroup$ – Pam Aug 12 '14 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Harald Hanche-Olsen Aug 12 '14 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.