# 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 ?

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
• 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. – Joshua Grochow 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