where $D \left({x}\right)$ is the sum of divisors. This sum comes from my work on the number of reducible monic cubics. This is a two part question. By writing out all the divisors $\tau \left({a}\right)$ in this sum I get $$\begin{equation*} \sum_{a = 1}^{N} \sum_{b = 1}^{\left\lfloor{N/a}\right\rfloor} \tau \left({b}\right) = \begin{array}{l} \tau \left({1}\right) + \tau \left({2}\right) + \tau \left({3}\right) + \tau \left({4}\right) + \cdots + \tau \left({N}\right) + \\ \tau \left({1}\right) + \tau \left({2}\right) + \tau \left({3}\right) + \cdots + \tau \left({\left\lfloor{\frac{N}{2}}\right\rfloor}\right) + \\ \tau \left({1}\right) + \tau \left({2}\right) + \tau \left({3}\right) + \cdots + \left({\left\lfloor{\frac{N}{3}}\right\rfloor}\right) + \\ \cdots \\ \tau \left({1}\right). \end{array} \end{equation*}$$

We see that there are $N$ sums of $\tau \left({1}\right)$, $\left\lfloor{N/2}\right\rfloor$ sums of $\tau \left({2}\right)$, $\left\lfloor{N/3}\right\rfloor$ sums of $\tau \left({3}\right)$, $\cdots$ to a single sum of $\tau \left({N}\right)$. Thus we can write

$$\begin{equation*} \sum_{a = 1}^{N} D \left({\left\lfloor{\frac{N}{a}}\right\rfloor}\right) = \sum_{a = 1}^{N} \left\lfloor{\frac{N}{a}}\right\rfloor \tau \left({a}\right). \end{equation*}$$

Question 1: Is there a simpler or more direct proof of this?

Question 2: Can this be solved in terms of known functions or can the sum be reduced.

For example, I am looking to compute values say up to ${10}^{12}$ with in seconds to minutes. With this sum of order $\mathcal{O} \left({N}\right)$ this is not feasible. A case that I have in mind is the sum over the number of divisors can be computed in order of $\mathcal{O} \left({\sqrt{N}}\right)$ instead of $\mathcal{O} \left({N}\right)$ time.


  • 2
    $\begingroup$ Your sum is $\sum_{a,b,c,abc\le N} 1= \sum_{n \le N} \tau_3(n)$ where $\zeta(s)^3= \sum_{n=1}^\infty \tau_3(n) n^{-s}$ $\endgroup$
    – reuns
    Sep 15, 2019 at 20:16
  • $\begingroup$ That is interesting because this sum originally came from $$\sum_{a = 1}^{N} \sum_{b = 1}^{N} \left[{a\, b \le N}\right] \left\lfloor{\frac{N}{a\, b}}\right\rfloor$$ $\endgroup$ Sep 15, 2019 at 21:07

1 Answer 1


Regarding the Question 1, I think that the $\#\{(a,b,c): 1\leqslant abc\leqslant N\}$ expression by @reuns, if not "simple" or "more direct", is at least "the most nicely-looking". As for the Question 2, I see an $\mathcal{O}(N^{3/4+\epsilon})$-time computation. It is based on the following two ideas: $$\{\lfloor N/a\rfloor : 1\leqslant a\leqslant N\}=\{n : 1\leqslant n\leqslant\sqrt{N}\}\cup\{\lfloor N/n\rfloor : 1\leqslant n\leqslant\sqrt{N}\};\\\lfloor N/a\rfloor=n\iff\lfloor N/(n+1)\rfloor<a\leqslant\lfloor N/n\rfloor.$$ These say we need only $\mathcal{O}(\sqrt{N})$ points $n$ to compute $D(n)$ at, and gives the coefficients of $D(n)$ in the sum being computed, after grouping equal terms. Moreover, the same argument applies to computing $D(n)$ itself. So, the time (in arithmetic operations, $\mathcal{O}(N^\epsilon)$ each) to compute $D(n)$ for all $n\leqslant\sqrt{N}$ is roughly $\sum_{n\leqslant\sqrt{N}}\sqrt{n}$, and, to compute $D\big(\lfloor N/n\rfloor\big)$ for all these $n$, is roughly $\sum_{n\leqslant\sqrt{N}}\sqrt{N/n}$. Both are of the claimed order.

  • 1
    $\begingroup$ I found an article from Richard Sladkey, "A Successive Approximation Algorithm for computing the Divisor Summary Function", June 18, 2012 arXiv:1206.3369v1 [math.NT] 15 June 2012 where he shows that the solution can be computed in $\mathcal{O}(N^{5/9})$ steps. The paper introduces restricted divisor sums for part of this calculation. $\endgroup$ Sep 30, 2019 at 22:21

You must log in to answer this question.

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