# Questions about assigning a probability to a randomly chosen large integer $n$ being prime

I heard this question a few days ago, so reciting from memory:

If I were to randomly choose an arbitrarily large positive integer $n$, could I write a function that determines the likelihood of it being prime?

Intuitively, what would it mean to assign a probability to an integer of being prime?

Edit 1

I'm not sure how to incorporate the prime-counting function into this.

Edit 2

Alright, so the page on the prime number theorem says that:

Informally speaking, the prime number theorem states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N), where ln(N) is the natural logarithm of N.

Looking through the references, though, I can't find a more formal proof. So I will revise my question.

For a random integer selected in the range of $0$ to some large integer $N$, prove that the probability the selected integer is prime is $\frac{1}{\ln{N}}$.

Edit 3

If the selected integer $n$ was prime, it's necessary that it has no prime factors $p\leq\sqrt{n}$. If we could find the probability that $n$ is divisible by $p$ as some function of $p$, then could we write$$\prod_{p=2}^{\sqrt{n}}\left(1-f(p)\right)$$where $f(p)$ is the probability that $n$ is divisible by $p$?

-

1
At the very least you would first have to define exactly what you mean by picking an integer at random. – Brian M. Scott Nov 10 '12 at 10:48

1
Is this a field of study? See probabilistic number theory. – Did Nov 10 '12 at 11:01
– Dan Brumleve Nov 10 '12 at 11:47

## 3 Answers

Care should be taken in the sense we take the "density" of primes.

The prime number theorem states that $$\pi(n)=\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\tag{1}$$ Thus, $$\begin{align} \pi(n(1+\alpha))-\pi(n) &=\frac{n(1+\alpha)}{\log(n)+\log(1+\alpha)}-\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\\ &=\frac{n(1+\alpha)}{\log(n)}-\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\\ &=\frac{\alpha n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\tag{2} \end{align}$$ Therefore, $$\frac{\pi(n(1+\alpha))-\pi(n)}{\alpha n} =\frac1{\log(n)}+O\left(\frac1{\alpha\log(n)^2}\right)\tag{3}$$ In the sense of $(3)$, the density of primes is $\dfrac1{\log(n)}$.

-

A very cool solution. Thanks! – rnmartingale Nov 10 '12 at 21:34

On your second question, what it might mean to assign a probability to the likelihood of a number being prime, you might want to take a look at this answer, the discussion in the comments under it, and in particular the book that I refer to there, Towards a Philosophy of Real Mathematics by David Corfield.

-

Thanks for the link, I'll take a day to read and understand what's going on before returning to this question. – rnmartingale Nov 10 '12 at 11:29

By the prime number theorem it is usually accurate to assume as a heuristic that the probability that $n$ is prime is about $\frac{1}{\log{n}}$.

-

1
Thanks for the reference, I should incorporate this into my question. – rnmartingale Nov 10 '12 at 10:58
But you have reworded the title in such a way that the question is less answerable. You might also like to consider the Riemann hypothesis and Cramér's conjecture. – Dan Brumleve Nov 10 '12 at 11:12

1
I'm sorry, I'm trying to avoid vagueness. How would you suggest I change my question? – rnmartingale Nov 10 '12 at 11:19
There is no easy way to narrow it down. I think vaguer is better. – Dan Brumleve Nov 10 '12 at 11:23
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9496573805809021, "perplexity_flag": "head"}