5
$\begingroup$

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 ?

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\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 Oct 30 '13 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 Oct 30 '13 at 19:15
  • $\begingroup$ You're right - I was being slow. I updated my answer to reflect the correct value. $\endgroup$ – Joshua Grochow Oct 30 '13 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$ – Joshua Grochow Oct 31 '13 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 Oct 31 '13 at 19:44

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.