<p>You can notice that there is <span class="math-container">$O(\sqrt{n})$</span> unique values in the set S = {<span class="math-container">$\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$</span>}. Therefore you can calculate the function in <span class="math-container">$O(\sqrt{n})$</span></p>
<p>Also since this function is asymmetric, you can even calculate x2 faster by using this formula: <span class="math-container">$D(n) = \overset{u}{\underset{x = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize - u^2$</span> for <span class="math-container">$u = \lfloor \sqrt{n} \rfloor $</span></p>
<p>Even more complex but faster: using the method that Richard Sladkey described in <a href="https://arxiv.org/abs/1206.3369" rel="nofollow noreferrer">this paper</a> you can calculate the function in <span class="math-container">$O(n^{1/3})$</span></p>

CC BY-SA 4.0
2021-08-26T19:27:55.957Z
2021-08-26T19:45:06.600Z
2021-08-26T19:45:06.600Z
Vo Hoang Anh
<p>Based on a "folkore intuition" for a related problem, one might expect this to be at least as hard as factoring: </p>

<p>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 <a href="https://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer">this related question</a>). $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)$.</p>

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

CC BY-SA 3.0
2013-10-30T13:50:52.847Z
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
CC BY-SA 3.0
2013-10-30T19:15:09.183Z
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
CC BY-SA 3.0
2013-10-30T20:16:50.630Z
You're right - I was being slow. I updated my answer to reflect the correct value.
Joshua Grochow
CC BY-SA 3.0
2013-10-31T16:57:16.373Z
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
CC BY-SA 3.0
2013-10-31T19:44:11.800Z
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
CC BY-SA 3.0
2013-10-31T20:14:48.803Z
I don't know how to do that - that's an interesting question. That's why in my previous comment I said "it's always easy to factor $d(n)$ *(given its value)*"
Joshua Grochow
CC BY-SA 3.0
2013-10-31T22:15:10.660Z
Ok ! Too bad we know so few things about such questions :)
Xoff
CC BY-SA 3.0
2013-10-29T21:26:01.780Z
2013-10-30T20:16:23.407Z
2017-04-13T12:57:54.777Z
Joshua Grochow
<p>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$.</p>

<p><a href="http://en.wikipedia.org/wiki/Divisor_summatory_function">The divisor summatory function</a> is defined by :
$$D(n)=\sum_{i=1}^n d(i)$$</p>

<p>This is <a href="https://oeis.org/A006218">sequence A006218</a> in OEIS.</p>

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

<time-complexity>
Computational Complexity of the Divisor summatory function
Xoff
# Computational Complexity of the Divisor summatory function

(Asked by: username_0 on 2013-10-28)

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](http://en.wikipedia.org/wiki/Divisor_summatory_function) is defined by :
$$D(n)=\sum\_{i=1}^n d(i)$$

This is [sequence A006218](https://oeis.org/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 ?

**Tags:** time-complexity


---

## 2 answers

### Answer by username_2 on 2013-10-29. Score: 9 | Accepted answer

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](https://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer)). $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$).

> **Comments:**
> **username_0**: 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$.  
> **username_0**: 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$.  
> **username_2**: You're right - I was being slow. I updated my answer to reflect the correct value.  
> **username_2**: 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.  
> **username_0**: 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  
> **username_2**: I don't know how to do that - that's an interesting question. That's why in my previous comment I said "it's always easy to factor $d(n)$ *(given its value)*"  
> **username_0**: Ok ! Too bad we know so few things about such questions :)  

---

### Answer by username_1 on 2021-08-26. Score: 2

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](https://arxiv.org/abs/1206.3369) you can calculate the function in $O(n^{1/3})$


---

