Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ n \ge 2$
A step-by-step solution will be helpful.
Thanks in advance.

share|cite|improve this question
Not sure if this is of any help but for the second some there exists an alternative form see this question: $\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=\sum_{k=1}^{n}d(k)$ where $d(k)$ denotes the number of divisors of $k$. – philipph Apr 15 '14 at 7:40
The second summation I gave is also know as Divisor Summatory Function. link gives a nice proof of that. What I'm worried about is the first problem. – Ansh Kumar Apr 15 '14 at 10:54
$\lceil \frac{n}{k}\rceil -\lfloor\frac{n}{k}\rfloor$ is $1$ when $k$ does not divide $n$ and $0$ otherwise. So the difference between the sums is $\sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil - \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor = -d(n)$ where $d(n)$ is the number of divisors of $k$. Finding a fast solution for one is finding a fast for both – Sylvain Biehler Apr 15 '14 at 11:07
@Bilou06 am i right in the following comment..? – Ansh Kumar Apr 15 '14 at 16:24

First add results for all k where the result is >= ceil (sqrt (n) + 1), that's about sqrt (n) values. Then for 1 <= m <= ceil (sqrt (n)), find exactly the set of integers k where the result is equal to m, and add m times the number of elements in that set. There are about sqrt (n) calculations for that as well, so a total of 2 x sqrt (n) calculations.

Since ceil (n/k - 1) for example is easier to calculate than the number of integers k for which ceil (n/k - 1) = m, this will be a bit faster if you don't make the switch at sqrt (n) but at some smaller value.

I doubt there is a closed solution, unless you count a sum as a closed solution.

share|cite|improve this answer
Can you explain your solution using an example, for convenience let us take n=10. Actually I'm not getting what you want to say. – Ansh Kumar Apr 15 '14 at 10:59
Wait a second are you suggesting me to use $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor = 2 \sum_{k=1}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{k} \right\rfloor - {\lfloor \sqrt{n} \rfloor}^2 -1$$ – Ansh Kumar Apr 15 '14 at 12:27

@Bilou06 No of pairs of x,y satisfying $ xy \le n $ is given by $$ \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 - {\lfloor \sqrt{n} \rfloor}^2 $$
but for $ xy \lt n $ no of pairs is given by $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k} - 1 \right\rceil $$
or it can be changed into $xy\le n-1 $ and let N = n-1, then no of pairs is given by $$ \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 - {\lfloor \sqrt{N} \rfloor}^2 = \sum_{k=1}^{n-1} \left\lceil \frac{n}{k} - 1 \right\rceil $$ am I right ??

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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