# Computational Complexity of the Divisor summatory function

The divisor function $d(n)$, is the number of $(a,b)\in\mathbb {N^+}^2$ such that $a\times b =n$. For example, $d(2)=2$ because $2=1\times 2=2\times 1$ and d(6)=4 because $6=1\times 6=2\times 3=3\times 2=6\times 1$.

The divisor summatory function is defined by : $$D(n)=\sum_{i=1}^n d(i)$$

This is sequence A006218 in OEIS.

Does anyone know the best time complexity algorithm to compute this function ? Are they any results published on the computational complexity of this function ?

Based on a "folkore intuition" for a related problem, one might expect this to be at least as hard as factoring:

The folkore intuition suggests that computing the number of prime factors, or even computing essentially any useful information about the prime factorization, is as hard as factoring itself (see Tao's answer to this related question). $d(n)$ gives you exactly such information, and is essentially equivalent (from the computational perspective) to computing $D(n)$, since $d(n) = D(n) - D(n-1)$.

For example, if $n$ is squarefree, then $d(n)$ is equal to $2^{f}$ where $f$ is the number of prime factors. For general $n$, $d(n)$ is $\prod_{p} (m_p + 1)$ where $m_p$ is the number of times the prime $p$ divides $n$ (that is, $n = \prod_{p} p^{m_p}$ is the prime factorization of $n$).

• I think that $d(n)=\prod_p(m_p+1)$ for all $n$. Thanks for your answer, I was hoping that at least on some values, D(n) could be guessed without computing all $d(i)$ $i\le n$.
– Xoff
Oct 30 '13 at 13:50
• I don't understand. $n=2$, $m_2=1$, and $m_p=0$ for all other primes p. Hence $d(2)=\prod_p(m_p+1)=2\times1\times1\times\dots=2$.
– Xoff
Oct 30 '13 at 19:15
• You're right - I was being slow. I updated my answer to reflect the correct value. Oct 30 '13 at 20:16
• BTW, although $d(n)$ can have roughly the same number of bits as $n$, it is always easy to factor $d(n)$ (given its value): since each $m_p \leq \log_2 n$, all of the prime factors of $d(n)$ have value at most $1 + \log_2 n$, so one can find all the prime factors of $d(n)$ in polynomial (in $\log n$ = the number of bits of $n$) time by brute force trial division. It may be difficult to use this factorization to actually compute the multiplicities $m_p$ - this seems like a variant of the NP-complete problem subset-sum - but I thought this was interesting anyways. Oct 31 '13 at 16:57
• This seems quite remarkable ! Could you please elaborate in your answer on how, from n, you can find the primes factor of $d(n)$ ? Thank you
– Xoff
Oct 31 '13 at 19:44

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

It is in randomized functional subexp.

Trial sieve algorithms subexponential number of times to factor. Gather all the prime factors and organize your sum as needed. There are at most $$o(\log n)$$ distinct prime factors and so complexity is at most subexponential.