Take the 2-minute tour ×
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.

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|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 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. –  user143055 Apr 15 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 –  Bilou06 Apr 15 at 11:07
    
@Bilou06 am i right in the following comment..? –  user143055 Apr 15 at 16:24

2 Answers 2

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|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. –  user143055 Apr 15 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$$ –  user143055 Apr 15 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|improve this answer

Your Answer

 
discard

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.