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 ?


2 Answers 2


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

  • 1
    $\begingroup$ 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$. $\endgroup$
    – Xoff
    Commented Oct 30, 2013 at 13:50
  • $\begingroup$ 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$. $\endgroup$
    – Xoff
    Commented Oct 30, 2013 at 19:15
  • $\begingroup$ You're right - I was being slow. I updated my answer to reflect the correct value. $\endgroup$ Commented Oct 30, 2013 at 20:16
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 31, 2013 at 16:57
  • $\begingroup$ 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 $\endgroup$
    – Xoff
    Commented Oct 31, 2013 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})$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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