4

Suppose $N$ is a (large) fixed positive integer, and one is asked to randomly choose any two integers (numbers could be same as well) from $1$ to $N$ (including $1$ and $N$). Let the experiment be repeated $M$ times and the choices of numbers be $\{a_1,b_1\},\dots,\{a_M,b_M\}$. Let $P_N(M)$ be the number of pairs $\{a_i,b_i\}$ whose sum $a_i+b_i$ is a prime. Define $P_N=\displaystyle Lim_{M\rightarrow \infty}(P_N(M)/M)$. Are there any results known for $P_N$ ?

user10001
  • 463

3 Answers3

2

It will be roughly $1/\log N$ since you're effectively choosing a random number near $N$. The exact number can be computed if you care to put in that much effort. For example, with $N=10^6$ the probability is 7.3056967061% (exactly, if I haven't made any mistakes), compared to the approximation 7.238...% you get with the log.

Charles
  • 32,122
  • If the choice of numbers is in the range $N_1$ to $N_2$ (where both $N_1$ and $N_2$ are 'large') then the probability will be roughly $N_2/((N_2-N_1)log(N_2))−N_1/((N_2-N_1)log(N_1))$. Right ? – user10001 Aug 31 '13 at 00:49
  • 1
    It would be roughly $\frac{1}{N_2-N_1}\int_{N_1}^{N_2}\frac{dx}{\log x}$, so a better estimate would be $\frac{\operatorname{li}(2N)}{2N}$. – Charles Sep 01 '13 at 13:36
  • A closer approximation to your situation would be $\frac{2}{N^2-2N}\int_2^{N}\frac{(x-1)dx}{\log x}$ since the numbers in the middle are more likely. A yet closer approximation is $\frac{1}{N^2-2N}\int_2^{N}\frac{(x-1)dx}{\log x}+\frac{1}{N^2-2N}\int_{N+1}^{2N}\frac{(2N+1-x)dx}{\log x}$. – Charles Sep 01 '13 at 13:44
2

Since you're taking the limit as $M \to \infty$, you're really asking for the exact probability that a given choice of two numbers from $1$ to $N$ will add up to give a prime. You need two ingredients to compute this. First, you need an approximation for the probability that $n$ is prime for a number $n$. This can be gleaned from a prime counting function, pointed out by another post. A fairly good approximation for the probability that $n$ is prime, as indicated, is $f(n) = 1 / \ln(n)$. Or even better is $f(n) = 1 / ((\ln (n \ln n) - 1) + (\ln \ln n - 2) / \ln n))$. Now you want to sum/integrate this from $n = 2,3,\ldots,2N$ assuming $n$ is the sum of two random numbers between $1$ and $N$. Note the probability of getting value $n$ from the 2 numbers you add is $(n-1)/N^2$ if $n \leq N$, and $(2N - n + 1)/N^2$ if $n > N$. So you can break up your sum/integral into two parts, and e.g. use numerical integration via Riemann-sum style methods for large enough $n$, or approximation using Taylor series of $f(n)$ for large enough $n$, say centered at some fairly large value of $n=n'$ and then also just using a computer to evaluate the probability for the first values of $n \leq n'$, using exact computation based on whether $n$ is prime or not.

user2566092
  • 26,142
1

Not sure but I think this may be of use: Prime-counting function

Mufasa
  • 5,434