• I
If I select two integers at random, what is the probability that their sum will be prime?

jedishrfu
Mentor
This is a tough question to answer since we have no formula for primes. The simplest approach would be to write a python program to do the work. It would need a list of primes and a range of numbers to start with.

As an example, the range of 1-10 then the highest prime is 19 ie 9+10 and so in general highest prime would be < 2N where N is the top number in the range of numbers 1-N. From there you can create estimates of the number of primes found between 1-10, 1-100, 1-1000 ...

Last edited:
Staff Emeritus
If I select two integers at random
What do you mean by this?

PeroK
hmmm27
Gold Member
If I select two integers at random, what is the probability that their sum will be prime?
Almost exactly the same as simply selecting one integer [edit: and testing that for primality].

jedishrfu
jedishrfu
Mentor
Except if you select one integer then the sum is 2N which will never be prime.

-vs-

1+1 = 2 , and 1+2 = 3, 1+4=5, 1+6=7...

Ahh so 1+ any selected integer to find the prime and then count the number of summing variations to get that prime.

hmmm27
Gold Member
LOL, no : I meant just pick any integer at random and see if it's prime : why bother picking two and adding them ?

berkeman and jedishrfu
jedishrfu
Mentor
I don't know if you can say that perhaps @fresh_42 can comment here.

fresh_42
Mentor
Picking two random integers or picking the sum directly is the same process. The number of primes less than ##x## is the function ##\pi(x)## and it is
$$\lim_{x \to \infty}\dfrac{\pi(x)}{\dfrac{x}{\ln (x)}}=1$$
Since you haven't restricted any range where we are looking for primes, we need to consider all integers. The relative frequency is thus
$$\dfrac{\pi(x)}{x} \sim \dfrac{1}{x}\cdot\dfrac{x}{\ln x}=\dfrac{1}{\ln (x)} \stackrel{x\to \infty }{\longrightarrow }0$$
The probability to pick a prime out of all integers is zero.

Abhishek11235, nomadreid, FactChecker and 3 others
FactChecker
Gold Member
The larger the random number is, the more likely that it has a divisor and that becomes practically certain in the limit. Furthermore, picking a natural number "at random" out of all the natural numbers implies that the picked number would tend to be HUGE. There is no limit to how huge.
To get a non-zero answer, we would have to limit the allowable selection to a finite subset.

fresh_42
Mentor
The probability within the first 1,000 numbers is about 1/7 by the formula and about 1/6 if counted. The formula is for large n.

I would think that the probability that the sum of a pair of randomly selected integers between ##n## and ##m## is prime would be a little smaller than the probability that an integer selected randomly between ##n## and ##m## will be prime. Because the expected value of the sum is larger, and the ratio of primes to integers decreases as the numbers get larger.

Here is a program you can use to try and test it:

Python:
import sympy
import random

n = 1
m = 100000000
N_ITER = 10000000

n_sum_primes = 0
n_single_primes = 0

for i in range( N_ITER ):
p1 = random.randint( n, m )
p2 = random.randint( n, m )
if( sympy.isprime( p1 ) ) :
n_single_primes += 1
if( sympy.isprime( p1 + p2 ) ) :
n_sum_primes += 1

print( n_sum_primes / N_ITER )
print( n_single_primes / N_ITER )

Going up to 1 million the probabilities look like this:

Last edited:
PeroK
Homework Helper
Gold Member
2020 Award
The probability to pick a prime out of all integers is zero.
This is not right, because you've wrongly assumed that the limiting case is a valid probability distribution. Which it is not.

If we select an integer ##n## uniformly from the range ##1-N##, then the probability that ##n## is selected ##p(n) = \frac 1 N##. And, clearly, ##p(n) \rightarrow 0## as ##N \rightarrow \infty##.

However, critically, the limiting case is not a valid probability distribution. We can see this as, in the limiting case of selection from all positive integers we have:

$$\sum_{n = 1}^{\infty}p(n) = \sum_{n = 1}^{\infty} 0 = 0$$
And you can see that the probability space is invalid in the case of the limit. In other words, a uniform probability distribution on ##\mathbb N## does not exist.

Note that we can have a uniform probability distribution on the continuous interval ##[0, 1]##, although not on all of ##\mathbb R##.

The correct answer is that there is no uniform distribution on the integers. The probability of selecting a prime tends to zero as the size of the range increases without bound. But, the limiting case of ##p(n) = 0## for all ##n## is not itself a valid solution.

jbriggs444
jbriggs444
Homework Helper
The correct answer is that there is no uniform distribution on the integers.
Indeed. Which means that we cannot properly pose the question about primes in the naturals as a question about probability.

What we can do is to pose it as a question about asymptotic density.

The asymptotic density of a subset S of the naturals is the limit (if it exists) as ##n## increases without bound of the number of elements of S in the range from 1 through ##n## as a fraction of ##n##.

As @fresh_42 has pointed out, the asymptotic density of the primes in the naturals is zero.

FactChecker and PeroK
Staff Emeritus
I would think that the probability that the sum of a pair of randomly selected integers between and is prime would be a little smaller than the probability that an integer selected randomly between and will be prime
He said randomly selected integers, not positive integers.

We are all discussing this assuming he meant something other than what he wrote. Different things.

Keith_McClary
Gold Member
The larger the random number is, the more likely that it has a divisor and that becomes practically certain in the limit. Furthermore, picking a natural number "at random" out of all the natural numbers implies that the picked number would tend to be HUGE. There is no limit to how huge.
To get a non-zero answer, we would have to limit the allowable selection to a finite subset.

What is the simplest proof that the density of primes goes to zero?

FactChecker
Gold Member
My post was just meant to be intuitive. I am not knowledgeable enough to give a formal proof. The others on this thread are more qualified to answer.

fresh_42
fresh_42
Mentor
My post was just meant to be intuitive. I am not knowledgeable enough to give a formal proof. The others on this thread are more qualified to answer.
Mine, too. Yes, there is no probability distribution and maybe we should have said likelihood instead of probability, or - as I did - relative frequency, or density of primes. And yes, the probability of picking one prime as opposed to a prime as a sum of finitely many integers from a finite set of integers may be slightly different, or not. Fact is, it doesn't matter.

The probability to pick a prime from a finite set of integers ##\{1,\ldots,n\}## is ##1/\ln n##. And, yes, I know that there are better boundaries, so this is again false. Sorry, I should have said: The probability to pick a prime from a finite set of integers ##\{1,\ldots,n\}## is roughly ##1/\ln n##. The larger ##n## is, the closer to ##1/\ln n## we get. Now, if we let those finitely many integers become more and more, the smaller are the odds to pick a prime. Uh! Got it. I should have said odds from the beginning.

And here is a special for all nitpickers: How many even prime integers are there?
$$\{-2,+2\}$$

FactChecker
Baluncore
If I select two integers at random, what is the probability that their sum will be prime?
You only need generate one random number.
The Riemann zeta function approximates the number of primes less than a given magnitude.
Select one random integer, evaluate the derivative of the RZF for that value, and you have the probability that a value of that magnitude will be prime.
Srinivasa Ramanujan also had a good approximation for the RZF.

sysprog
PeroK
Homework Helper
Gold Member
2020 Award
You only need generate one random number.
The Riemann zeta function approximates the number of primes less than a given magnitude.
Select one random integer, evaluate the derivative of the RZF for that value, and you have the probability that a value of that magnitude will be prime.
I think you mean the prime counting function? The RZF is something else.

That said, if you select an integer and the last digit is not ##1,3,7## or ##9##, then the probability it is prime is zero. With one notable exception.

Baluncore
That said, if you select an integer and the last digit is not 1, 3, 7 or 9, then the probability it is prime is zero. With one notable exception.
All primes are odd, with the exception of 2, which must make 2 the oddest prime of all.

Staff Emeritus
With one notable exception.
And one less-notable exception.

Baluncore