# On the sum of sum of divisors $\sum_{a=1}^{N} D \left({\left\lfloor{\frac{N}{a}}\right\rfloor}\right)$.

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.

Thanks

• 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}$ – reuns Sep 15 at 20:16
• 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$$ – Lorenz H Menke Sep 15 at 21:07

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 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.
• 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. – Lorenz H Menke Sep 30 at 22:21