2
$\begingroup$

Compared to the number of integers and the number of primes, how many safe primes are there?
Specifically, I'd like to be able to estimate how many safe primes there are below a given number.

1 Answers 1

6

These are very closely related to Sophie Germain primes (if $p$ and $2p+1$ are prime, $2p+1$ is called a safe prime and $p$ is called a Sophie Germain prime.)

An estimate of the counting function for Sophie Germain primes was given by Hardy and Littlewood. It is easy to turn this into an estimate of the counting function for safe primes.

The estimate is based on informal "probabilistic" reasoning.
The estimate for Sophie Germain primes has the shape $Cn/(\ln n)^2$ where $C$ is an explicit constant. So informally, the answer is "there are lots." But the estimate is speculative. It has not even been proved that there are infinitely many safe primes!

However, the Hardy-Littlewood estimate, conjectural though it may be, seems to fit actual data fairly (but not spectacularly) well.

  • 0
    @jnm2: I voted up on your behalf! ;-)2011-06-11