Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Someone once told me (rather testily) that we cannot speak of the "probability that a number is prime" because the sequence is deterministic. I think I understood his point but would like to make sure. There is a theorem in Stopple's Primer of Analytic Number Theory (p. 97):

The probability that a large integer $N$ is prime is about $\dfrac{1}{\log N}$.

Of course, a large integer N is either prime or it is not. Its status is completely determined by its predecessors.

As long as we are careful to define the sample space, is there anything here that is controversial? Are there other probability-related objections to Stopple's theorem?

Thanks for any insight.

Edit: This was a pedagogical device, not a theorem, as the answers below (and Stopple) make clear.

share|improve this question
    
Regarding the deleted sentence: Why the "gratuitous use of blue", anyway? :) You can format it as a blockquote instead by preceding it with a >. –  Rahul Jul 11 '12 at 21:49
    
@RahulNarain: Ah. Thanks. I hadn't tried out the color function, so it was just an experiment. –  daniel Jul 11 '12 at 21:50

2 Answers 2

up vote 7 down vote accepted

I don't think the statement is meant to be taken literally, but one can interpret these statements as about a random integer between 1 and N, or between N and 2N if you want. Stopple is just trying to give you some insight into the prime number theorem: for instance 1 out of every 100 or so integers of size about e^100 is prime.

share|improve this answer

Speaking of the "probability that a number is prime" is less of a specific fact but more of a guiding principle. A lot of things can be quickly derived by applying this principle, and when a pleasing (alleged) fact is discovered, one can look for a more rigorous proof if one so desires.

As an example, consider computing the sum

$$ \sum_{p \leq n} \frac{1}{p}. $$

Applying the principle that a number $k$ is prime with probability $1 / \log k$, then the 'expected' value of the sum is

$$ \sum_{p \leq n} \frac{1}{p} \approx \sum_{k = 2}^{n} \frac{1}{k \log k} \approx C_1 + \int_2^n \frac{dx}{x \log x} = C_2 + \log \log n $$

where $C_1$ and $C_2$ are some constants. This turns out to be the correct answer, in the sense that the difference of the two sides converges to $0$ if $C_2$ is chosen to be the Meissel-Mertens constant.

share|improve this answer
    
If I had read further I would have seen that this, as you say, was Stopple's idea. I haven't exactly reached p.90 of Apostle yet, but I also see your note is in accord with the material there. –  daniel Jul 11 '12 at 23:41
1  
I used this idea and an estimate on the prime counting function in my answer to this question (+1) –  robjohn Jul 12 '12 at 0:27

Your Answer

 
discard

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.