Listing All the Composite Numbers

The Sieve of Eratosthenes is a process of the gradual elimination of composite numbers from a list of all positive integers. First one removes all the multiples of 2, then all the multiplies of 3, and so on. The prime numbers are the ones that remain.

Curiously enough, it is possible to arrange all the composite numbers in a table with a single swoop and not by a step-by-step process. In this case the prime numbers are those that have been left over.

The applet below shows one playful approach to accomplishing this task.

With the "Show n" box checked, the applet displays a table of integers that are arranged according to the following rules:

1. The first row contains the terms of the arithmetic series 4, 7, 10, 13, ..., i.e., the numbers computed from the formula 4 + 3k, k = 0, 1, 2, ...,

2. These same numbers are listed in the first column,

3. Each subsequent row displays an arithmetic sequence with a difference that is increased by 2: the second row has the difference 5, the third 7, and so on.

With this arrangement, we can make a statement.

Theorem

An integer x > 2 is prime if and only if the number n = (x - 1) / 2 does not appear in this table.

To see why this is true, check the "Show x" box. The numbers that will be displayed are obtained from x = 2n + 1, with n's in the previous table. What do you see?

When the box "Show x" is checked, the table displays all the odd composite numbers. The first row contains the multiples of 3, the second of 5, the third of 7, and so on. Missing are the even number which are all composite any way (except for 2, of course) and all odd primes. All other numbers are in the table.

References

1. C. S. Ogilvy and J. T. Anderson, The Book of Numbers, Oxford University Press, 1966, 98-99

|Contact| |Front page| |Contents| |Arithmetic| |Store|

Copyright © 1996-2012 Alexander Bogomolny