summation of ceil and floor function

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

Observation

Finding a closed form for $\sum_{k=1}^{n} \lfloor\frac{n}{k}\rfloor$ will be incredibly significant, if it is possible.

It will also mean that a closed form is possible for $\sum_{k=1}^{n} \lceil\frac{n}{k}\rceil$

If you combine these two sums in the following way: $$f(n)=\sum_{k=1}^{n} \lfloor\frac{n}{k}\rfloor - \sum_{k=1}^{n} \lceil\frac{n}{k}\rceil + n$$ You have a function f that counts the number of divisors of n.

Why is this significant? Well, if you put in any positive integer C and the sum equals 2, it means C is prime. Because it has only 2 divisors, 1 and C.

This means that Deterministic Primality Testing can be done in constant time. With the fastest deterministic, unconditional algorithm to date being polynomial is the AKS Primality Test.

Even better, lets update our function to: $$f(C, n)=\sum_{k=1}^{n} \lfloor\frac{C}{k}\rfloor - \sum_{k=1}^{n} \lceil\frac{C}{k}\rceil + n$$

If you plot this function for a given positive integer C, it will have a staircase form with the amount of steps equal to the number of divisors of C.

Because of the staircase form of f, it will be possible to output all the divisors of C in approx. log(C) evaluations of f, which on our modern day computers is pretty much instant. With the fastest general integer factorization algorithm being the General Number Field Sieve.

Congratulations, we have then solved the Integer Factorization problem.

If these sums do not have closed forms, we still have Shor's Algorithm that is going to run on upcoming quantum computers that will be able to do Integer Factorization in polynomial time.

Answer 4

$\overset{n - 1}{\underset{i = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize = \overset{n}{\underset{i = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize - 1 = D(n) - 1$

You can notice that there is $O(\sqrt{n})$ unique values in the set S = {$\lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{3} \rfloor, \dots, \lfloor \frac{n}{n - 1} \rfloor, \lfloor \frac{n}{n} \rfloor$}. Therefore you can calculate the function in $O(\sqrt{n})$

Also since this function is asymmetric, you can even calculate x2 faster by using this formula: $D(n) = \overset{u}{\underset{x = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize - u^2$ for $u = \lfloor \sqrt{n} \rfloor $

Even more complex but faster: using the method that Richard Sladkey described in this paper you can calculate the function in $O(n^{1/3})$