MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $d(n)$ denote the number of divisors of $n$. Is it known that the series $$\sum_{p \text{ prime}} \frac{1}{d(p-1)}$$ diverges?

This would follow immediately from the Sophie Germain Conjecture. Indeed, if there are infinitely many primes of the form $2p+1$ ($p$ a prime), then infinitely many terms of the series are equal to $1/4$, so the series doesn't even satisfy the most basic requirement for convergence! So, surely there must be a direct proof?

share|cite|improve this question
See Igor's answer for an argument along the lines you want. – Gjergji Zaimi Apr 25 '13 at 5:43
FYI: Since $1/d(n)$ is a multiplicative function that is $1/2$ on every prime, standard heuristics predict that the summatory function $\sum_{n\le x} 1/d(n)$ should have order of magnitude $x(\log x)^{1/2-1}$. (One could probably even write down the leading constant if careful.) On the further heuristic that random shifted primes $p-1$ aren't all that different from random $n$, one predicts that $\sum_{p\le x} 1/d(p-1)$ should have order of magnitude $x(\log x)^{-3/2}$. – Greg Martin Apr 25 '13 at 7:52
Interesting, @Greg - thanks for sharing. – Bruno Joyal Apr 27 '13 at 22:36
up vote 8 down vote accepted

Since every divisor $k$ of $p-1$ either satisfies $k\le \sqrt{p-1}$ or $\frac{p-1}{k}\le \sqrt{p-1}$, we have $d(p-1) \le 2\sqrt{p-1}$. If we let $p_n$ denote the $n$th prime, then since $p_n-1 \le n^2$ for all $n$ (an easy consequence of the prime number theroem...), we have

$\sum_{n=1}^N \frac{1}{d(p_n-1)} \ge \sum_{n=1}^N\frac{1}{2n} \ge \frac{\ln N}{2}$,

so the partial sums diverge.

Obviously one can get much better bounds than these.

share|cite|improve this answer
Cool! Thanks zeb! – Bruno Joyal Apr 25 '13 at 5:57
Nitpick: the prime number theorem has as an easy consequence the fact that $p_n-1\le n^2$ for all sufficiently large $n$. – Greg Martin Apr 25 '13 at 7:41

Answering my own question, because I totally overlooked the following ridiculous idea:

Obviously $d(n)\leq n$ for every $n$. Thus $d(p-1)\leq p-1 < p$, so $1/d(p-1) > 1/p$ and the divergence follows from the divergence of $\sum 1/p$ (if one is willing to assume that).

share|cite|improve this answer

I did a heuristic analysis to study how this sum is growing. I calculated $d(p_n-1)$ and the sum and plotted the curve of the sum vs $n$. I obtained a very smooth curve which looked like a cumulative distribution curve. Next I did curve fitting to model this curve where the sum is the dependent variable and $n$ is the independent variable. The boundary condition I imposed was that the sum should be divergent. The following model was found to best fit the desired sum.

$$ \sum_{n=1}^{x}\frac{1}{d(p_n - 1)} \sim e^{a + b/x + c\ln x} $$

where $a,b$ and $c$ are suitable constants.

The true asymptotic formula could be different from the above but I believe this can give some hints in the direction of the true asymptotics.

share|cite|improve this answer
Thank you, Nilotpal. – Bruno Joyal Apr 27 '13 at 22:48
Presumably your $N$ and $x$ are the same. Note that $e^{a+b/x+c\ln x} = e^a x^c e^{b/x} \sim e^a x^c$. So your model is simply predicting that the sum is asymptotic to a constant times a power of $x$. This is almost surely false: the sum is bounded above by $cx/\log x$ by the prime number theorem, and bounded below by $cx/(\log x)^2$ if there are infinitely many Sophie Germaine primes. As I commented on the original post, the sum is probably asymptotic to a constant times $x(\log x)^{-3/2}$. – Greg Martin Apr 28 '13 at 2:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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