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 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 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 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 circuit, a solution had been found. Lehmer sieves were very fast, in one particular case factoring
2 93 + 1 = 3 × 3 × 529510939 × 715827883 × 2903110321 {\displaystyle 2^{93}+1=3\times 3\times 529510939\times 715827883\times 2903110321}
in 3 seconds. The original is lost, but an early-1980s reconstruction is at the Computer History Museum. 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 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 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 (and the Bicycle Sieve replica) 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.
Early work independent of Lehmer In 1896 F. W. Lawrence published the paper "Factorisation of numbers". In its final section it outlines a design for an automated, electromechanical digital computing device which could apply the sieving method described in the paper. In 1910 a French translation was published by André Gérardin in his journal Sphinx-Oedipe: this sparked a number of efforts to build devices on the lines of Lawrence's description. In February 1912 Gérardin reported in Sphinx-Oedipe that Maurice Kraitchik had built a mechanical prime sieve. According to Hugh C. Williams and Jeffrey Shallit its design is "rather similar to that of Lawrence" (Kraitchik already knew about Lawrence's paper when his machine was announced, though he did not acknowledge a connection.) According to Shallit, Williams and François Morain, while Kraitchik's machine "might have worked reasonably well at low speeds, it would very likely have been useless at higher speeds". In March Gérardin also announced the existence of two other machines, one designed by Pierre Carrisan and the other by himself. But according to Shallit, Williams and Morain "[a]ll three of these early attempts to construct a sieve suffered from the same inadequacies: they existed only as roughly constructed prototypes, were rather inefficient, required the human eye to scan for solutions, and produced no significant results—apparently none whatsoever." However during 1913-14 Eugène-Olivier Carissan, who had previously built the machine of his brother Pierre's design, designed and built a new prototype. Its performance was encouraging and so a precision version was ordered from the Paris horologists Chateau Frères et Cie. World War I delayed production and so the final machine à congruences ("congruence machine") was only completed in 1919. This machine was electro-mechanical but hand-cranked. It was able to prove 1,321,442,641 prime in 15 minutes of operation and prove 18,405,321,661 prime in 1 hour of operation. According to Williams and Shallit "[t]his seems to have been the first automatic sieve mechanism to have ever been successfully constructed." Shallit, Williams and Morain judged the 1926 Lehmer sieve to be "in many ways much less sophisticated" (though in fact it is somewhat faster). Since 1994 the 1919 Carissan machine has been in the collection of the Musée des Arts et Métiers. It was displayed at the Société d'encouragement pour l'industrie nationale's large Paris exhibition of calculating machinery in June 1920. Eugène-Olivier had plans for improvements including motor-driven operation, but it seems these were not carried out: both Carissan brothers died by 1925 and the machine fell into obscurity over time. D. H. Lehmer did not hear of the Carissans until 1989. He was aware of Lawrence and Kraitchik by at least 1934, when he described their designs for machines as "impractical ... [though] theoretically interesting" even though, according to Williams and Shallit, Lehmer's 1932 gears sieve "represents in many ways the fruition of their ideas". Similarly Gérardin was, according to Richard F. Lukes, "apparently totally unaware of Lehmer's previous work" when he constructed a new number sieve in 1937. This was reported to be an electrically-powered, automatic device incorporating a printer. Based on a photograph Lukes speculated that it was based on an adding machine.
… excerpt ends here. Continue reading the full article.
