Lehmer Sieves
by Dr. Michael R. Williams
Head Curator - The Computer History Museum
Building T-12A
Moffett Federal Airfield
Mountain View, California 94035
U.S.A.
printed here by permission of the authorThe name of Lehmer is famous in the mathematical sieve process because two different Lehmers were involved. D. N. Lehmer was the father and D. H. Lehmer (the one who did the work with the mechanical sieves in the Computer History Museum) was the son.
Everyone thinks of the mathematical sieve process as the method that Eratosthenes used (about 276 BC) to find prime numbers. This is only one special case of the general sieve process. The general process is a powerful tool in that area of mathematics known as algebraic number theory. The full process involves taking two sets of numbers and trying to find a number X (in a certain range) that is a remainder when the numbers in the first set are divided by those in the second (some other conditions also apply-see end of this description). Because a simple version of this problem was solved by early Chinese mathematicians, it is sometimes known as the "Chinese Remainder Theorem" or the "Czechoslovakian system," because Antonin Svoboda used it in 1955.
The original "bicycle chain" sieve (the one we have is a replica) was made in the student’s shop in LeConte Hall (University of California, Berkeley) in 1926. Essentially the machine consisted of a number bicycle chains (the number used depended on how big the first set of number was). The values of certain remainders of interest are represented by a rod sticking out of the side of specific links in each chain. As the chains rotate around the drive axle at the top, these rods will close small electrical switches (note the wires attached to the electrical switch which get hit as the chain rotates). When all switches get closed at once, an electrical signal can travel down the complete length of the machine—this signals that a solution has been found to the specific problem being considered.
This bicycle chain system could search through the numbers represented on the chains at a rate of 60 per second. This was actually fastest numerical-type machine of its day.
The 1936, home made, sieve using 16mm movie film punched with holes is another device that is identical in operation to the bicycle chain system. This time the chains are replaced with loops of film of various lengths, the holes representing the remainders of interest. The brass bolts at the top once held brushes that would make contact with the lower roller when a hole was at the top of its rotation. If a complete set of holes was detected across the top, then the machine had found a solution.
The geared sieve dates from 1932 when it was set up to demonstrate the technique at the Chicago exhibition known as the "Century of Progress Exposition." It is made up of gears of different sizes representing numbers in exactly the same way that the bicycle chains or strips of movie film were of different length. Holes in each gear represented various remainders when these numbers were divided by others and they could be plugged up with toothpicks to only leave a certain set of these numbers open. A bright light on one side of the machine would shine on the gears and, if the holes lined up, then it would reach the other side and trip a flip-flop attached to the photocell – perhaps the first time that an electronic flip-flop was used in a computing device (they had been used earlier in counters for cosmic rays and this is what gave Lehmer the idea). The output of the flip-flop was amplified and would be used to stop the motor spinning the wheels – thus allowing you to see the solution to the problem. The amplifier gave them a lot of trouble because it had to amplify many millions of times to stop the motor quickly.
The gear sieve could check 5,000 combinations in one second – it was only some time in the early 1960s when computers were fast enough to match these speeds (they would actually have to do the divisions – a slow process). If you avoid the dividing and represent the bicycle chains by long sequences of bits (in which a "1" counts as a rod on a link and a "0" counts as a regular link) and then rotate these bit strings doing an "and" on them each shift, then an IBM 7094 could (and did) manage to check 100,000 numbers per second, but required some real fancy programming to do it.
Lehmer later used some Navy surplus delay lines (not mercury but solid state) to store bit strings representing the remainders ("0" = not a remainder of interest, "1" = a remainder of interest) and built a machine using them. As the bits came out of the delay line they could be put through an "and" circuit to check for a solution at the rate of 1,000,000 per second. In the 1970s he constructed one from integrated circuit shift registers that could work at 20 million per second.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The types of problems that Lehmer was attempting to solve can be most easily seen when considering a polynomial in two variables and what you want to find is values of x and y so that:
F(x,y) = 0 This is a very wide class of problems and is, in general, very difficult except in special cases.
You could always check each value of x and each value of y within a given range to see if it works as a solution to the problem, but that is particularly time consuming if the polynomial is large.
If you plug in values of x and y and that gives a value z for the polynomial, then each time the value of x is increased by m the remainder when z is divided by m does not change. Gauss showed that if you had a polynomial like F(x,y) = 0, then it was easy to find a set of conditions (which can be implemented on a sieve) involving specific sets of numbers m and other conditions for finding values of x and y.
Thus a sieve can be used to solve what are known as Diophantine equations in two variables. The prime number sieve of Eratosthenes can be thought of as a special case of this more general problem.
The actual problems that Lehmer was trying to solve were described by him as:
In a sieve problem you are given two numbers A and B as well as k integers or moduli
m1, m2 m3, …mk
and k other integers
n1, n2, …nk
and finally a matrix
{ aij} where 1 £ i £ k and 1 £ j £ ni
and the problem is to find an unknown integer X such that
X º ai1 or ai2 or ai3 …aini (mod mi) for all i between 1 and k
So that X is congruent to one of the ni residue classes (mod mi) specified in rows of the triangular matrix. The final condition is simply that A < X < B
The sieve problem is then to find all those integers satisfying the two kinds of conditions, congruential conditions and inequalities. At times the problem is to find the smallest value of X satisfying those conditions.