2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – philipph
    Commented Apr 15, 2014 at 7:40
  • $\begingroup$ 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. $\endgroup$
    – Vedanshu
    Commented Apr 15, 2014 at 10:54
  • 1
    $\begingroup$ $\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 $\endgroup$ Commented Apr 15, 2014 at 11:07
  • $\begingroup$ @Bilou06 am i right in the following comment..? $\endgroup$
    – Vedanshu
    Commented Apr 15, 2014 at 16:24
  • $\begingroup$ You can pull the $-1$ out of the ceiling. $\endgroup$
    – user65203
    Commented Aug 12, 2017 at 14:34

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This does not provide an answer. $\endgroup$
    – mlc
    Commented Aug 12, 2017 at 14:52
  • $\begingroup$ @mlc Unless the answer is incorrect, it explains why a closed form solution cannot exist which answers a part of the question. $\endgroup$
    – Halil Sen
    Commented Jan 13, 2021 at 10:43
1
$\begingroup$

$\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})$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Vedanshu
    Commented Apr 15, 2014 at 10:59
  • $\begingroup$ 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$$ $\endgroup$
    – Vedanshu
    Commented Apr 15, 2014 at 12:27
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .