Lehmer sieve

Lehmer sieve

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. Lehmer sieves are mechanical devices that implement sieves in number theory, the sieve of Eratosthenes being perhaps the most well known example.

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 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 chains of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switches, and when all the switches were closed simultaneously, creating a complete electrical curcuit, 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.

References

*citation
first = D. N. | last = Lehmer | authorlink = Derrick Norman Lehmer
title = Hunting big game in the theory of numbers
journal = Scripta Mathematica
year = 1932
volume = 1
pages = 229–235
url = http://ed-thelen.org/comp-hist/Lehmer-NS03.html
.

*citation
first = D. H. | last = Lehmer | authorlink = Derrick Henry Lehmer
journal = American Mathematical Monthly
title = The mechanical combination of linear forms
volume = 35 | issue = 3 | pages = 114–121 | year = 1928
url = http://www.jstor.org/view/00029890/di991103/99p12522/0
. [http://ed-thelen.org/comp-hist/Lehmer-NS-01.html Also online] at the Antique Computer home page.

*citation
first = Albert H. | last = Bleiler
title = Recreations in the Theory of Numbers
publisher = Dover | year = 1964
, chap.XX,XXI.

External links

* [http://ed-thelen.org/comp-hist/Mike-Williams-Lehmer.html Lehmer Sieves, by Dr. Michael R. Williams, Head Curator of The Computer History Museum]
* [http://www.computerhistory.org/virtualvisiblestorage/artifact_main.php?tax_id=01.01.06.00 The Computer History Museum page about Lehmer Sieves]
* [http://groups.google.sh/group/sci.math/msg/bbe87db07b43cf2f A modern Lehmer sieve]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… …   Wikipedia

  • Derrick Henry Lehmer — Born February 23, 1905(1905 02 23) Berkeley, California Died May 22, 1991(1991 05 22) (aged&# …   Wikipedia

  • Derrick Norman Lehmer — Born July 27, 1867(1867 07 27) Somerset, Indiana, United States Died September 8, 1938(1938 09 08) Berkeley, California, United States Education …   Wikipedia

  • Derrick Lehmer — Derrick Henry Lehmer (* 23. Februar 1905 in Berkeley (Kalifornien); † 22. Mai 1991 ebenda) war ein US amerikanischer Mathematiker, spezialisiert auf Zahlentheorie. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften …   Deutsch Wikipedia

  • Derrick Henry Lehmer — (* 23. Februar 1905 in Berkeley (Kalifornien); † 22. Mai 1991 ebenda) war ein US amerikanischer Mathematiker, spezialisiert auf Zahlentheorie. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften …   Deutsch Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • General number field sieve — In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n (consisting of log2 n bits) is of …   Wikipedia

  • Riesel Sieve — is a distributed computing project, running in part on the BOINC platform. Its aim is to prove that 509203 is the smallest Riesel number, by finding a prime of the form k · 2 n −1 for all odd k smaller than 509203.Progress of the projectAt the… …   Wikipedia

  • Lucas-Lehmer-Riesel test — The Lucas Lehmer Riesel test is a primality test for numbers of the form N=k 2^n 1, with 2^n > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer test for Mersenne numbers.The algorithmThe algorithm is very similar to… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”