Partial Divisor Summatory Function Calculation

Question

I'm aware that $D(n)$ can be calculated in O(sqrt(n)) time. Can $ D(n, k) $ also be calculated in O(sqrt(n)) time? What's the best algorithm?

For example, if $n = 8$ and $k = 3$, then $ D(n, k) = \lfloor{\frac{8}{1}}\rfloor + \lfloor{\frac{8}{2}}\rfloor + \lfloor{\frac{8}{3}}\rfloor $

Answer 1

You meant $$\sum_{a,b, ab\le n, a \le k}1 = \sum_{a \le k} \left\lfloor \frac{n}{a} \right\rfloor$$

Then yes it can be computed in $O(\sqrt{n})$ operations because $$\left\{\left\lfloor \frac{n}{a} \right\rfloor, a \ge 1\right\}$$ contains at most $2 \sqrt{n}+1$ elements and

$\left\lfloor \frac{n}{a} \right\rfloor = c \iff \frac{n}{a} = c+r, r \in [0,1)$

$\iff n= ca+ra, a =\frac{n}{c+r}$

$\iff a \in (\frac{n}{c+1},\frac{n}{c}]$ so $\left\lfloor \frac{n}{c}\right\rfloor-\left\lfloor \frac{n}{c+1}\right\rfloor$ many choices for $a$

This way we obtain $$ \sum_{a \le k} \left\lfloor \frac{n}{a} \right\rfloor = \sum_{a =1}^{ \min(\lfloor \sqrt{n}\rfloor,k)} \left\lfloor \frac{n}{a} \right\rfloor+ \sum_{c=\lfloor n/k\rfloor}^{\lfloor n/\lfloor \sqrt{n}\rfloor\rfloor-1} \min(k,\left\lfloor \frac{n}{c}\right\rfloor)-\min(k,\left\lfloor \frac{n}{c+1}\right\rfloor)$$

Answer 2

Yes you can, I also have a problem that require this function to be calculated fast enough.

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})$, even with partial divisor summatory function.

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