On Prime Numbers

by John R. Carlsen

On August 6, 2002, a trio of authors at the Indian Institute of Technology, Kanpur released for review an impressive paper titled Primes is in P, in which they present a (potential) relatively-fast algorithm for testing a given number for primality. One of my outstanding mathematics professors from St. Edward's University, Dr. Michael Engquist, brought this paper to my attention hardly more than a week after its publication. This renewed my interest in prime numbers.

Why Are Prime Numbers Important?

Among other areas, prime numbers are very import to cryptography (the science of encoding and decoding messages to create relative security in communication). Modern cryptographic practices (such as R.S.A. encryption) rely upon the selection of relatively unknown (and usually very large) prime numbers. Using these cryptographic methods, those able to identify larger prime numbers should, in theory, be better able to securely encode their own messages and to decode their adversaries' messages.

What Are Prime Numbers?

Prime numbers are numbers that can only be divided evenly (that is, divided with no remainder) by 1 (the multiplicative identity) and the number itself. So, for any given prime number p, n divides p if and only if n is equal to either 1 or p. Using mathematical notation, this may be expressed as:

n | p, n = { 1, p }

As an example, I created (programatically) the following table of prime numbers in the interval [1,1000], of which there are 169. In the table, composite (non-prime) numbers appear in cells with grey backgrounds and the numbers along the right side keep a running total of the number of prime numbers within the interval through the end of each line.

The Prime Numbers In the Interval [1,1000]

How Many Prime Numbers Are There?

As there are infinitely many numbers, there are infinitely many prime numbers. However, the number of prime numbers in a finite interval is also finite, and the proportion of prime numbers in an interval quickly becomes smaller as the interval becomes larger.

Methods For Approximating Numbers of Primes

In discussing how to build modern electronic versions of the 1926 D. H. Lehmer bicycle-chain sieve (an electromechanical device designed to select numbers to test for primality), my long-time mentor LaFarr Stuart taught me to represent the number of primes in any closed interval [1,n] as the function Pi(n). He also taught me the (n / ln n) method to approximate Pi(n).

The (n / ln n) Method

The first method I used to approximate the number of primes on an interval [1,n] was

After generating a table of several thousand prime numbers with my Apple iMac, I found that this doesn't provide a very good approximation. (My old iMac with only a 600 MHz PowerPC G3 processor running my quick-and-dirty C++ program tests for primality and prints only about 4000 numbers a minute, using Euclid's algorithm to find the greatest common denominator of the number under test.) Running my little program for about 10 minutes, I found that:

My (n / 2 log n) Method

Looking at a table of these numbers, I started wondering how many of the numbers in a given interval are prime. This was a simple matter of dividing Pi(n) by n. I realized then (based on work I performed 2002/08/15) that there seems to be a pretty apparent – perhaps even obvious – relationship between the magnitudes of n and Pi(n):

Simply by counting the number of zeros in the values for n above, which yields log n, I realized that it was half the denominator of my approximation of Pi(n). This is surprisingly simple and appears to yield a much closer approximation of Pi(n) than the (n / ln n) method, as shown below:

Refining Methods for Approximating Pi(n)

Though the percentage error using my (n / 2 log n) method is much less than that of the previous method, this method of approximation tends to overstate rather than understate how many prime numbers are in a given range. What causes me even more concern, however, was the apparent divergence (increasing error as n increases) of these approximations. The previous method tended to converge, which is preferable, so I re-evaluated that method.

I found that I could greatly reduce the error in the (n / ln n) method by multiplying the result by the scalar 10/9, so the resulting approximation formula would look like this:

The results obtained from this method compare favorably to those obtained via the methods discussed previously, as indicated via the table below.

Summary

As indicated in the table above, the approximation obtained by using my (10 n / 9 ln n) method is much closer to the actual number of primes. In addition, though the values used here for n are relatively small (six digits, vs. the largest known prime number having roughly one million digits), the margin of error seems to get smaller as n gets bigger, so this approximation appears to converge upon the correct answer as n increases.