For a positive integer $k$, let $d(k)$ be the number of divisors of $k$. So $d(1)=1$, $d(p)=2$ if $p$ is a prime, $d(6)=4$, and $d(12)=6$.

What are the precise asymptotics of $\sum_{k=1}^n 1/(k d(k))$?


1) This came up on the side in the polymath5 project.

2) There, Tim Gowers wrote: If nobody knows the answer, maybe that’s one for MathOverflow, where I imagine a few minutes would be enough.

3) Asked: 14:17 Jerusalem time. (The first accurate answer: 17:44 Jerusalem time.)

4) Looking only at primes or only at integers with a typical number of divisors suggested a $\log\log n$ behavior, but looking at semiprimes indicates the sum is larger. I don't know how much larger.

5) I couldn't find an answer on the web. If there is an easy way searching for an answer that I missed this will be interesting too.

Follow up:

Great answers! Thanks. What about the sum $\sum_{k=1}^n 1/(kd^2(k))$ ?

  • $\begingroup$ SUM_{k=1}^n 1/kd(k) ... Does that mean $\sum_{k=1}^n 1/(k d(k))$ or $\sum_{k=1}^n d(k)/k$ ? $\endgroup$ – Gerald Edgar Mar 17 '10 at 12:45
  • $\begingroup$ The former, according to Gil's link. $\endgroup$ – Steve Huntsman Mar 17 '10 at 12:47
  • $\begingroup$ It's a sum of multiplicative functions so should be amenable to using Dirichlet series. $\endgroup$ – Victor Miller Mar 17 '10 at 13:01
  • 2
    $\begingroup$ The correct guess is C*(log N)^(1/2). Look-up the Selberg-Delange method. (The point is that sum(z^w(n), n <= X) ~ C*(log X)^(z-1) and (1/2)^w(n) is essentially the same as 1/d(n), so by partial summation we get sum(1/kd(k),k <= X) ~ C*(log X)^(1/2-1+1)) $\endgroup$ – maks Mar 17 '10 at 15:43
  • 2
    $\begingroup$ Re: the followup. If the hypotheses of the Delange (or Raikov) Tauberian theorem are satisfied, then $\sum_n 1/(n d(n)^2)$ should be $\sim C (\log x)^{1/4}$, since if $p$ is prime, $d(p) = 2$. $\endgroup$ – Victor Miller Mar 18 '10 at 10:38

The idea (from the Selberg-Delange) method to doing this problem is the following steps:

1) Let $F(s) = \sum_{n\ge 1} \frac{1}{n^s d(n)} = \prod_{p} \left(1 + \sum_{k=1}^{\infty} \frac{1}{(k+1) p^{ks}} \right)$. The latter is by multiplicativity of $d(n)$.

2) If we look, instead at $G(s) = \prod_p \left( 1 + \frac{1}{2 p^s} \right)$ we can see that $F(s)/G(s)$ has a non-zero limit as $s \rightarrow 1$ from above. $G(s)$ corresponds in our original sum to restricting $n$ to be square-free.

3) $G(s)^2$ almost looks like $\zeta(s)$. Show that $G(s)^2/\zeta(s)$ also has a non-zero limit at $s \rightarrow 1$.

4) You then use some Tauberian theorems to show that since $H_n \sim \log n$ (which is the sum associated with $\zeta(s)$ then the corresponding sum for $G(s)$ (i.e. over the square-free $n$) is $\sim to \sqrt{\log n}$.

| cite | improve this answer | |
  • $\begingroup$ I might be wrong, but I believe this idea predates Selberg and Delange by almost half a century. This was done already in 1908 by Landau to find the number of numbers represented by a sum of two squares. But since Selberg-Delange has been mentioned quite a few times in this post, I am doubting myself. $\endgroup$ – Dror Speiser Mar 17 '10 at 20:52
  • $\begingroup$ @Dror: Yes, I was reminded of the Landau result you quoted too. I think what Delange did was to give a Tauberian theorem that was strong enough to deduce things like the following: $F(s) = \sum_n \frac{a_n}{n^s}$. and $F(s)^r/\zeta(s)$ has a non-zero limit when $s \rightarrow 1$, for some integer $r$ then $sum_{n \le x} a_n \sim C (\log x)^{1/r}$ for some non-zero $C$. Ramanujan's paper only announces the results. It doesn't have any proofs. $\endgroup$ – Victor Miller Mar 17 '10 at 21:40
  • 1
    $\begingroup$ The Tauberian theorem you mention was actually proved by Raikov: "Generalisation of a theorem of Ikehara–Landau (in Russian). Mat. Sbornik, 45 (1938)". If I am not mistaken, the Selberg-Delange method is more about getting a better error term (dating 1947?). Of course the particular instance of Landau was also proved and can be found in: "Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate." Arch. Math. Phys. 13, 305-312, 1908. $\endgroup$ – Dror Speiser Mar 17 '10 at 21:52
  • 1
    $\begingroup$ Suppose $D(s)$ is a Dirichlet series with multiplicative coefficients. If $D(s)=\zeta(s)^{a}F(s)$ where $a$ is rational and $F(s)$ is an Euler product which converges without zeros or poles in $\mathrm{Re}(s)> \delta$ for some $\delta < 1$, then you do NOT need a Tauberian theorem to study partial sums of the coefficients of $D(s)$. It is enough to apply a usual contour integration argument, but instead of shifting the whole contour you deform it around the singularity at $s=1$. The partial sums end up being $~c(\alpha)X(\log{X})^{a-1}$ where I forget $c(a)$ (it is simple). $\endgroup$ – David Hansen Mar 18 '10 at 16:15
  • $\begingroup$ ("\alpha" should be "a") $\endgroup$ – David Hansen Mar 18 '10 at 16:16

The correct asymptotic is $C \cdot (\log N)^{1/2}$. (c.f Selberg-Delange method).

| cite | improve this answer | |
  • $\begingroup$ Nice answer! I wishes I knew more about Selberg Delange method. $\endgroup$ – Gil Kalai Mar 17 '10 at 18:34
  • $\begingroup$ The main contribution to the sum will come from the integers n <= N, with (1/2)loglog N + O((loglog N)^(1/2 + epsilon)) prime factors. This is again a consequence of... the Selberg-Delange method. $\endgroup$ – maks Mar 17 '10 at 20:53


The answer can be extracted from a paper of Ramanujan, "Some formulae in the analytic theory of numbers", no. 17 in his collected papers. There he gives, among other things, the formula

$\sum_{n\leq X} \frac{1}{d(n)} \sim \frac{X}{\sqrt{\log{X}}}\pi^{-\frac{1}{2}}\prod_{p}\sqrt{p^2-p}\log{\frac{p}{p-1}}$.

The answer to the original question can be extracted from this by partial summation.

As for the "follow-up", the answer is $\sum_{n \leq X} \frac{1}{n d(n)^2} \sim C (\log{X})^\frac{1}{4}$. Again, Selberg-Delange...

| cite | improve this answer | |
  • 1
    $\begingroup$ That's a nice formula, but Gil asked about the sum of 1/(n d(n)). $\endgroup$ – Michael Lugo Mar 17 '10 at 15:48
  • 5
    $\begingroup$ Partial summation. $\endgroup$ – David Hansen Mar 17 '10 at 15:52
  • 3
    $\begingroup$ Even though it is very elementary, I think you should write the above comment in the actual answer. The way it is currently written is just annoying. $\endgroup$ – Dror Speiser Mar 17 '10 at 18:06
  • 2
    $\begingroup$ Does Ramanujan give a proof or just the formula? $\endgroup$ – François G. Dorais Mar 17 '10 at 18:25
  • 8
    $\begingroup$ A remark for those who, like me, were confused: $\sqrt{p^2-p} = p (1-1/(2p)+O(1/p^2))$ and $\log (p/(p-1)) = 1/p + 1/(2 p^2) + O(1/p^3)$ so the factors in the product are $1+O(1/p^2)$ and the product converges. $\endgroup$ – David E Speyer Mar 17 '10 at 18:50

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.