2
$\begingroup$

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

$\endgroup$
  • 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 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$ – Lorenz H Menke Sep 15 at 21:07
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.