4
$\begingroup$

If I shoot in the dark and pick a random number that's $, what's the probability that the number will be prime? How many guesses, on average, would it take to get a prime number?

I would really like to understand the reasoning behind the answer, and not just a one-line formula.

1 Answers 1

4

Assuming that by picking a random number less than $n$ you mean randomly picking a natural number less than $n$ with uniform distribution over all such numbers, the answer is

$$\frac{\pi(n-1)}{n-1}\;,$$

where $\pi$ is the prime-counting function, since $\pi(n-1)$ of the $n-1$ numbers you're choosing from are prime. That article has a lot of information on that function, which it wouldn't make sense to reproduce here; feel free to ask if there's more you want to know that you can't find there.

The average number of trials until the first success given a probability $p$ of success is $1/p$, so the average number of trials in this case would be

$$\frac{n-1}{\pi(n-1)}\;.$$

  • 0
    And for large $n$ that average number of trials is asymptotic to $1/\log n$.2011-10-27
  • 5
    @Gerry, number of trials is (asymptotic to) $\log n$ -- it cannot be less than 1. The reciprocal is the probability in each trial.2011-10-27
  • 0
    Thanks. Assuming we use Gerry's approximation, would the average number of trials be log n or (log n)/2 ?2011-10-27
  • 0
    @Mark: As Henning wrote, it's asymptotic to $\log n$. Why do you think it might be $(\log n)/2$?2011-10-27
  • 1
    Apologies to all for that $1/\log n$. Henning, thanks.2011-10-27
  • 0
    @joriki I'm probably getting confused by the word "average" that it should be divided by 22011-10-28
  • 1
    @Mark: No, the averaging has already been done. Dividing by $2$ only applies if you average two quantities. If you average $n$ quantities, you have to divide by $n$, and in the present case, the "average" should more properly be called the [expected value](http://en.wikipedia.org/wiki/Expected_value), which is a probabilistic generalization of an average.2011-10-28