Tuesday, October 22, 2019

Probability of Randomly Choosing a Prime Number

Probability of Randomly Choosing a Prime Number Number theory is a branch of mathematics  that concerns itself with the set of integers. We restrict ourselves somewhat by doing this as we do not directly study other numbers, such as irrationals. However, other types of real numbers are used. In addition to this, the subject of probability has many connections and intersections with number theory. One of these connections has to do with the distribution of prime numbers. More specifically we may ask, what is the probability that a randomly chosen integer from 1 to x is a prime number? Assumptions and Definitions As with any mathematics problem, it is important to understand not only what assumptions are being made, but also the definitions of all of the key terms in the problem. For this problem we are considering the positive integers, meaning the whole numbers 1, 2, 3, . . . up to some number x. We are randomly choosing one of these numbers, meaning that all x of them are equally likely to be chosen. We are trying to determine the probability that a prime number is chosen. Thus we need to understand the definition of a prime number. A prime number is a positive integer that has exactly two factors. This means that the only divisors of prime numbers are one and the number itself. So 2,3 and 5 are primes, but 4, 8 and 12 are not prime. We note that because there must be two factors in a prime number, the number 1 is not prime. Solution  for Low Numbers The solution to this problem is straightforward for low numbers x. All that we need to do is simply count the numbers of primes that are less than or equal to x. We divide the number of primes less than or equal to x by the number x. For example, to find the probability that a prime is selected from 1 to 10 requires us to divide the number of primes from 1 to 10 by 10. The numbers 2, 3, 5, 7 are prime, so the probability that a prime is selected is 4/10 40%. The probability that a prime is selected from 1 to 50 can be found in a similar way. The primes that are less than 50 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47. There are 15 primes less than or equal to 50. Thus the probability that a prime is selected at random is 15/50 30%. This process can be carried out by simply counting primes as long as we have a list of primes. For example, there are 25 primes less than or equal to 100. (Thus the probability that a randomly chosen number from 1 to 100 is prime is 25/100 25%.) However, if we do not have a list of primes, it could be computationally daunting to determine the set of prime numbers that are less than or equal to a given number x. The Prime Number Theorem If you do not have a count of the number of primes that are less than or equal to x, then there is an alternate way to solve this problem. The solution involves a mathematical result known as the prime number theorem. This is a statement about the overall distribution of the primes and can be used to approximate the probability that we are trying to determine. The prime number theorem states that there are approximately x / ln(x) prime numbers that are less than or equal to x. Here ln(x) denotes the natural logarithm of x, or in other words the logarithm with a base of the number e. As the value of x increases the approximation improves, in the sense that we see a decrease in the relative error between the number of primes less than x and the expression x / ln(x). Application of the Prime Number Theorem We can use the result of the prime number theorem to solve the problem we are trying to address. We know by the prime number theorem that there are approximately x / ln(x) prime numbers that are less than or equal to x. Furthermore, there are a total of x positive integers less than or equal to x. Therefore the probability that a randomly selected number in this range is prime is (x / ln(x) ) /x 1 / ln(x). Example We can now use this result to approximate the probability of randomly selecting a prime number out of the first billion integers. We calculate the natural logarithm of a billion and see that ln(1,000,000,000) is approximately 20.7 and 1/ln(1,000,000,000) is approximately 0.0483. Thus we have about a 4.83% probability of randomly choosing a prime number out of the first billion integers.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.