# summation of ceil and floor function

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.

-
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

## 2 Answers

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.

-
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 ??

-