Syncopated Systems^{®}
Comprehensive Computer Technology Solutions

Home  Library  Contact 
On Prime NumbersOn 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) relativelyfast 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 (nonprime) 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.
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 PrimesIn discussing how to build modern electronic versions of the 1926 D. H. Lehmer bicyclechain sieve (an electromechanical device designed to select numbers to test for primality), my longtime 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) MethodThe 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 quickanddirty 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) MethodLooking 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 reevaluated 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.
SummaryAs 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. 
Syncopated attempts to present a model Web site that meets or exceeds all applicable technical and legal requirements, including those of the A.D.A., COPPA, ICANN and W3C.  Syntax validated 
Style sheet validated 
Highest accessibility 
"Syncopated Systems" and "Syncopated Software" are registered trademarks of, the interlaced tuning forks and "recreate reality" devices are trademarks of, and all contents (except as otherwise noted) copyright ©20042008 the Syncopated Software Development Corporation. ALL RIGHTS RESERVED. Any reproduction without written permission or other infringement is prohibited by United States and international laws.  