Lehmer sieve
Encyclopedia
Lehmer sieves are mechanical devices that implement sieves
in number theory
. Lehmer sieves are named for Derrick Norman Lehmer
and his son Derrick Henry Lehmer
. The father was a professor of mathematics
at the University of California, Berkeley
at the time, and his son was to follow 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 equation
s or to factor
numbers. A Lehmer sieve will signal that such solutions are found in a variety of ways depending on the particular construction.
The first Lehmer sieve in 1926 was made using bicycle chain
s of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switch
es, and when all the switches were closed simultaneously, creating a complete electrical circuit
, a solution had been found. This version could test 60 number combinations a second.
Built in 1932, a device using gears was shown at the Century of Progress Exposition
in Chicago
. These had gears representing numbers, just as the chains and film 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 5000 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 design has been used to design sieves in integrated circuits or software.
Sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
in number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
. Lehmer sieves are named for Derrick Norman Lehmer
Derrick Norman Lehmer
Derrick Norman Lehmer was an American mathematician and number theorist....
and his son Derrick Henry Lehmer
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer was an American mathematician who refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes...
. The father was a professor of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
at the time, and his son was to follow 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 equation
Diophantine equation
In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations...
s or to factor
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
numbers. A Lehmer sieve will signal that such solutions are found in a variety of ways depending on the particular construction.
The first Lehmer sieve in 1926 was made using bicycle chain
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 simply for aesthetics. Nickel also confers a measure of...
s of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switch
Switch
In electronics, a switch is an electrical component that can break an electrical circuit, interrupting the current or diverting it from one conductor to another....
es, and when all the switches were closed simultaneously, creating a complete electrical circuit
Electrical network
An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, transmission lines, voltage sources, current sources and switches. An electrical circuit is a special type of network, one that has a closed loop giving a return path for the current...
, a solution had been found. This version could test 60 number combinations a second.
Built in 1932, a device using gears was shown at the Century of Progress Exposition
Century of Progress
A Century of Progress International Exposition was the name of a World's Fair held in Chicago from 1933 to 1934 to celebrate the city's centennial. The theme of the fair was technological innovation...
in Chicago
Chicago
Chicago is the largest city in the US state of Illinois. With nearly 2.7 million residents, it is the most populous city in the Midwestern United States and the third most populous in the US, after New York City and Los Angeles...
. These had gears representing numbers, just as the chains and film 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 5000 combinations a second.
In 1936, a version was built using 16 mm film
16 mm film
16 mm film refers to a popular, economical gauge of film used for motion pictures and non-theatrical film making. 16 mm refers to the width of the 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
Computer History Museum
The Computer History Museum is a museum established in 1996 in Mountain View, California, USA. The Museum is dedicated to preserving and presenting the stories and artifacts of the information age, and exploring the computing revolution and its impact on our lives.-History:The museum's origins...
. Since then, the same basic design has been used to design sieves in integrated circuits or software.