Lehmer sieves are mechanical devices that implement

sieves A sieve, fine mesh strainer, or sift, is a device for separating wanted elements from unwanted material or for controlling the particle size distribution of a sample, using a screen such as a woven mesh or net or perforated sheet material. T ...

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...

. Lehmer sieves are named for Derrick Norman Lehmer and his son

Derrick Henry Lehmer Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and ...

. The father was a professor of mathematics at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

at the time, and his son followed in his footsteps as a number theorist and professor at Berkeley. A sieve in general is intended to find the numbers which are remainders when a set of numbers are divided by a second set. Generally, they are used in finding solutions of Diophantine equations or to

factor Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, suc ...

numbers. A Lehmer sieve will signal that such solutions are found in a variety of ways depending on the particular construction.

Construction

The first Lehmer sieve in 1926 was made using

bicycle chain A bicycle chain is a roller chain that transfers power from the pedals to the drive-wheel of a bicycle, thus propelling it. Most bicycle chains are made from plain carbon or alloy steel, but some are nickel-plated to prevent rust, or simpl ...

s of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical

switch In electrical engineering, a switch is an electrical component that can disconnect or connect the conducting path in an electrical circuit, interrupting the electric current or diverting it from one conductor to another. The most common type of ...

es, and when all the switches were closed simultaneously, creating a complete electrical circuit, a solution had been found. Lehmer sieves were very fast, in one particular case factoring ::

2^ + 1 = 3 \times 3 \times 529510939 \times 715827883 \times 2903110321

in 3 seconds.

W. W. Rouse Ball Walter William Rouse Ball (14 August 1850 – 4 April 1925), known as W. W. Rouse Ball, was a British mathematician, lawyer, and fellow at Trinity College, Cambridge, from 1878 to 1905. He was also a keen amateur magician, and the founding ...

(1960) ''Lehmer's Machine'', in Mathematical Recreations and Essays, Macmillan, New York, pp 61-62. Built in 1932, a device using gears was shown at the

Century of Progress Exposition A Century of Progress International Exposition, also known as the Chicago World's Fair, was a world's fair held in the city of Chicago, Illinois, United States, from 1933 to 1934. The fair, registered under the Bureau International des Expositi ...

Chicago (''City in a Garden''); I Will , image_map = , map_caption = Interactive Map of Chicago , coordinates = , coordinates_footnotes = , subdivision_type = Country , subdivision_name ...

. These had gears representing numbers, just as the chains had before, with holes. Holes left open were the remainders sought. When the holes lined up, a light at one end of the device shone on a photocell at the other, which could stop the machine allowing for the observation of a solution. This incarnation allowed checking of five thousand combinations a second. In 1936, a version was built using 16 mm film instead of chains, with holes in the film instead of rods. Brushes against the rollers would make electrical contact when the hole reached the top. Again, a full sequence of holes created a complete circuit, indicating a solution. Several Lehmer sieves are on display at the Computer History Museum. Since then, the same basic idea has been used to design sieves in integrated circuits or

software Software is a set of computer programs and associated software documentation, documentation and data (computing), data. This is in contrast to Computer hardware, hardware, from which the system is built and which actually performs the work. ...

References

External links

by Dr. Michael R. Williams, Head Curator of The Computer History Museum
Lehmer sieves at Computer History Museum
(at the bottom of the page) History of computing hardware *History of computing hardware Perforation-based computational tools

Construction

See also

References

Further reading

External links