The probability that two integers picked at random are Prime.

362 Views Asked by At

It's known that The probability that two integers m and n picked at random are relatively prime is $\frac{6}{\pi^2}$

To see for myself, I ran 100,000,000 random tests of $gcd(m=random(), n=random())$ (random max 32767) and the probability was 60.09% (approx $\dfrac{6}{\pi^2}$).

Also ran a similar test that accepts two "random" integers, then tallies any prime pairs it encounters and the probability was 1.15% (approx $\dfrac{0.11}{\pi^2}$).

Question, is there a known approximation for primes as there is for coprimes?

Just curious.

Thanks.

EDIT

Based upon the comments, "Randomly chosen positive integers less than $n$ would be fine." I'll try playing with increasing values of $n$ (currently set to $32767$) to see how it tends to $0$ as $n$ tends to infinity. Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

It is a nontrivial thing to define a good idea of "randomly chosen integer", as @JMoravitz notes. The normal way to do this is to definite the density of a subset $S \subset \mathbb{Z}_{\geq 1}$ as $$ \lim_{N \to \infty} \frac{ \#(S \cap \{n | 1\leq n \leq N \} ) }{N}$$

With this idea in mind, the only thing to do is recall the prime number theorem that $\pi(N) \sim N/\log(N)$ (i.e., $\pi(N) = N/\log(N) + O(N)$ ) where $\pi$ is the prime counting function. Then we have the density of prime numbers is $$\lim_{N \to \infty} \pi(N)/N $$ which tends to $1/\log(N)$ which tends to zero, as $N \to \infty$.

From here I'll leave it to you as an exercise to show that the concurrent primality you are asking about is "rarer" (in our sense of density - which I stress is not a probability, so don't use those rules).