0
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Prime_number_theorem $\endgroup$
    – JMoravitz
    Jan 24, 2021 at 22:38
  • 1
    $\begingroup$ That said, "randomly chosen integers" doesn't make sense by itself. "Randomly chosen positive integers less than $n$" would be fine. You are able to uniformly at random select a positive integer less than $n$. You could also talk about the limiting behavior of such a probability as you take the limit as $n\to\infty$. There does not exist a uniform distribution over a countably infinite set however so you may not "pick an integer uniformly at random". $\endgroup$
    – JMoravitz
    Jan 24, 2021 at 22:40
  • $\begingroup$ Interesting this $\frac{11}{\pi^2}$, but what is the definition of the function "primes(rand(),rand())" ? $\endgroup$
    – NN2
    Jan 24, 2021 at 23:15
  • $\begingroup$ It's a function that accepts two "random" integers, then tallies any prime pairs it encounters. $\endgroup$
    – vengy
    Jan 24, 2021 at 23:34
  • $\begingroup$ I assume that $1.150655$ is, like $60.099903$, a percentage. In which case, it's not actually $\frac{11}{\pi^2}$ but closer to $\frac{0.11}{\pi^2}$, which is reasonable for something that, in reality, is supposed to be tending to $0$ for a large range. $\endgroup$ Jan 25, 2021 at 0:24

1 Answer 1

3
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .