A question about primes

  • I
  • Thread starter donglepuss
  • Start date
  • #1
10
1
If I select two integers at random, what is the probability that their sum will be prime?
 

Answers and Replies

  • #2
13,177
7,078
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:
  • #3
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
27,661
11,883
If I select two integers at random
What do you mean by this?
 
  • #4
hmmm27
Gold Member
848
392
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].
 
  • #5
13,177
7,078
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.
 
  • #6
hmmm27
Gold Member
848
392
LOL, no : I meant just pick any integer at random and see if it's prime : why bother picking two and adding them ?
 
  • Like
  • Haha
Likes berkeman and jedishrfu
  • #8
15,763
14,054
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.
 
  • Like
  • Informative
Likes Abhishek11235, nomadreid, FactChecker and 3 others
  • #9
FactChecker
Science Advisor
Gold Member
6,643
2,691
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.
 
  • #10
15,763
14,054
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.
 
  • #11
795
670
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:

Figure_1.png
 
Last edited:
  • #12
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
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.
 
  • #13
jbriggs444
Science Advisor
Homework Helper
10,369
4,964
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.
 
  • Like
Likes FactChecker and PeroK
  • #14
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
27,661
11,883
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.
 
  • #15
Keith_McClary
Gold Member
678
1,254
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?
 
  • #17
15,763
14,054
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\}$$
 
  • Like
Likes FactChecker
  • #18
Baluncore
Science Advisor
10,081
4,438
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.
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
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.
 
  • #20
Baluncore
Science Advisor
10,081
4,438
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.
 
  • Haha
Likes berkeman, Vanadium 50 and PeroK
  • #21
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
27,661
11,883
With one notable exception.
And one less-notable exception.
 
  • #22
Baluncore
Science Advisor
10,081
4,438
The unique prime factors of -30 are; ( 2, 3, -5 ) or ( 2, -3, 5 ) or ( -2, 3, 5 ) or ( -2, -3, -5 ).
I guess all four must be the unique factors.
 
  • #23
15,763
14,054
The unique prime factors of -30 are; ( 2, 3, -5 ) or ( 2, -3, 5 ) or ( -2, 3, 5 ) or ( -2, -3, -5 ).
I guess all four must be the unique factors.
(2,3,5),(-2,-3,5),(2,-3,-5) and (-2,3,-5) can also be considered as prime factors. Up to units means that units can be arbitrarily distributed.
 

Related Threads on A question about primes

  • Last Post
Replies
2
Views
623
Replies
1
Views
2K
Replies
1
Views
1K
  • Last Post
2
Replies
26
Views
2K
  • Last Post
Replies
8
Views
7K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
17
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
9
Views
2K
Top