Peter Alfeld --- Department of Mathematics --- College of Science --- University of Utah

The Prime Machine

A prime number is a natural number greater than 1 that can be divided without remainder only by itself and by 1. Natural numbers n that can be divided by a number less than n and greater than 1 are composite numbers. The prime machine finds prime numbers using the Sieve of Eratosthenes and lets you study and explore those prime numbers.

When you first click on the above applet a control window pops up. It should look like this:

The most important item in that window is the text field in the center of the second row, the one with the fetching dark red background. Everything happens with respect to the number in that field. Let's call it N. Initially, N=100 (that value lets you explore the prime numbers in a familiar range).

Let's go though the rows of the control panel.

1. Row 1.
   • The green buttons scroll down or up through the internally computed (rather than downloaded!) list of prime numbers. The number of angular brackets determines the speed of the scroll:
     • < or >: a step of 1 down or up; respectively.
     • << or >>: down or up to the next prime number.
     • <<< or >>> : down or up all the way to the end of the current list. The lower end is of course the smallest prime number, i.e., 2.
   • The gray or red button STOP will interrupt a computation of new primes that might be in progress.
   It is effective only when it is red.
   • The blue button quit will cause all computation to stop and the control window to disappear. You can achieve the same affect by clicking on the applet, or typing "x", "X", "q", or "Q" in the control window.
   • The yellow button draw causes a drawing to be displayed that illustrates the distribution of prime twins and the prime number theorem. More on that below.
   • The Status Label displays the following types of information:
     • Green, with the word "Ready". This means all is ready for a new computation.
     • Red, possibly with a number in it. This means the Sieve of Eratosthenes is being used to compute prime numbers. The number in the red field indicates the estimated number of seconds to completion. That number changes as time passes, but the estimate is not very reliable. It's usually too high, unless your computer is swapping heavily.
     • Blue, possibly with a number in it. This means that the information in the white text labels of the control display are being recomputed. The number indicates the estimated number of seconds to completion. It is computed only once, and not very reliable either.
     • Magenta, possibly with the word Memory in it. This means that in the last attempt to extend the range of prime numbers your computer ran out of memory. The program will attempt to restore the display and the list of primes to the previous values. If that does not work then everything is returned to the the default values (corresponding to N=100.
2. Row 2. N is the number around which everything revolves. You can change it via the green buttons in row 1, or you can just edit the text window. To the left of N (unless N=2 ) is the largest prime number less than N and to the right (unless we are right at the limit of the current range) is the smallest prime number greater than N . The window to the right turns gray if there is no prime number between N and the end of the current range, and the window to the left turns gray when N=2.
3. Row 3. This label exhibits the closest Prime Twins above and below N. A prime twin is a pair of prime numbers that differ by 2. Although this question has been much studied, nobody knows how many prime twins there are. There may be finitely many or infinitely many. If you figure out the answer, be sure to drop me a message so I can update this page!
4. Row 4 is devoted to illustrating the prime number theorem. phi is the number of primes less than or equal to N. N/log(N), where log is the natural logarithm, denotes an approximation of phi that is known to get arbitrarily accurate, in the sense that the ratio phi/(N/log(N)) converges to 1 as N goes to infinity. That ratio is displayed. For the range of numbers that this applet can handle (up to N = a few tens of millions) the ratio is almost constant and varies from about 1.12 to 1.06.
5. Row 5 shows the prime factorization of N.
6. Row 6 is dedicated to the Goldbach Conjecture which asserts that every even number greater than 2 can be written as the sum of two prime numbers. If N>2 is even then this row displays the following information:
   • The number of ways in which N can be written as the sum of two prime numbers.
   • Two prime numbers that add to N. Initially this is the pair where the two prime numbers are as close together as possible. However, you can scroll up and down the list using the + and - buttons.
   Nobody knows if the Goldbach conjecture is true or not, even though countless mathematicians and probably millions of high school kids have tried to settle the question. But as in the case of the number of prime twins, do let me know if you find the answer. I'll be pleased to make your acquaintance.
7. Row 7. I increase the version number by an appropriate amount every time there is a significant change. The run number indicates the number of times this program was activated since November 7, 1996.

How does it work?

When starting up the applet computes all prime numbers from 2 to 2N. It does this by using a modification of the Sieve of Eratosthenes that only considers odd numbers and is about twice as fast and uses half as much memory as the original sieve. As mentioned above, the default value of N is 100. If the value of N (perhaps entered though the textfield) exceeds the range of numbers covered a new computation is started automatically. The larger the new value of N, the longer the computation will take, and the more memory it will require.

A Graphical Illustration of the Prime Number Theorem

The celebrated Prime Number Theorem states that

                       number of primes <= N
           lim         --------------------- = 1.
       N-->infinity          N/log(N)

where log denotes the natural logarithm. It is pretty amazing to have such a tight connection exists between areas of mathematics (logarithms and prime numbers) that seem so disparate! For more information consult any text on Number Theory, for example those listed on my Prime Number Page.

Unfortunately, the ratio N/log(N) behaves very much like a linear function, so the large scale behavior of prime numbers is not readily apparent. You can display the number of prime twins, phi, and N/log(N) by pressing the yellow draw button in the first row of the control panel. (Press the button again to make the drawing disappear.)

For N=10,000 you get the display illustrated in the nearby figure. N varies along the horizontal axis. Red indicates the number of prime twins, green the approximation x/log(x) (counted from the horizontal axis, and blue the actual number of primes (also counted from the horizontal axis). Think of red being in front of green, and green in front of blue. You can only see the top of blue and the top of green, but all of red. According to the prime number theorem, in the limit as N tends to infinity green and blue become identical. It also appears from the picture that the number of prime twins grows linearly with N which, if true, would imply that there are infinitely many prime twins. Click here or on the picture to see the corresponding display for N=100,000,001 which is close to the largest value that I can reasonably handle on my machine. It actually does not look much different, although the blue wedge is a little narrower. You may also like to explore drawing the picture for small values of N, to illustrate the discrete nature of the prime distribution.

Note: If your machine is at all like mine then everything will become sluggish and things may not work quite right if you use a lot of memory. So you may want to be careful about choosing very large values of N.

Running Standalone and Downloading

You may download the byte code of this software and incorporate it into your own web pages or run it on your system in a standalone mode. You need the following Java classes:
• Prime.class
• ControlPrime.class
• DrawTheorem.class

When you click on these links (which point to binary files) you'll probably see something strange on your system. However, you should be able to download the files properly in spite of their appearance.

Prime is the class that calls all others. To run the software in standalone mode on a Unix system just type java Prime in the directory that contains your class files. If you want to base an Applet on your files make sure you specify the code base (the directory containing your class files) similarly as in the html code of this page. The code base must be accessible over the net, otherwise you get a security exception and things don't work right.

If you do download the software I invite you to let me know so that I can put you on my mailing list and inform you about future improvements. Of course, also let me know if you have any troubles.

There is no help information built into the program (at least not yet). This page is intended to be the documentation for the program. So you may want to copy the page, print it, or provide a link to it.

Known Bugs

• When the applet is run from inside a browser, clicking twice on the applet makes the control window disappear and reappear with resized text labels that may be too small for subsequent computation. To overcome this do the computation for N as large as you wish, and then click twice on the applet again.

---

[14-Aug-1997]

Return to Peter Alfeld's Home Page.

Designed for netscape and Java.