Lehmer sieve

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.

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 \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 in Mountain View, California. • Illustration — A Lehmer sieve using gears 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. The machine could then be wound backwards to find the point at which the light had shone, 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.

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.

In 1945 and 1946 D. H. and Emma Lehmer gained early experience with the vacuum-tube digital computer ENIAC at the University of Pennsylvania. In the next two decades D. H. Lehmer and others would devote significant attention to writing software sieves for general-purpose computers. However, on his return home to Berkeley Lehmer also decided to seek to build a fast special-purpose hardware sieve using vacuum tube logic. In an unpublished 1946 document he proposed a design for such a sieve, naming it the "Electronic Sieve": it would have been able to be reconfigured by plugging and unplugging logic modules. The proposal also lays out his idea for an "Acoustic Sieve" in which, in Lukes' words, "the periodic element would be a tube of ethylene glycol with a piezo-electric crystal at each end". Lehmer and Berkeley engineering professor Paul Morton did, at some point between 1946 and 1964, design and build all or part of a sieve using counters. After about two years' work they gave up this effort and instead turned their attention to working with delay line memory. In 1962 D. G. Cantor, G. Estrin, A. S. Fraenkel and R. Turn proposed another electronic sieve: this one would have used shift registers and been capable of being connected to a general-purpose computer, but was never built.

Lehmer and Morton's DLS-127, the initial form of the Delay Line Sieve, began operations in 1965 or 1966. The DLS-127 was built as an unsponsored educational project of Berkeley's Departments of Mathematics and Electrical Engineering at a cost of about US$2000, including a total of about $150 for its navy-surplus wire delay lines. The machine used the innate delay of delay-line memory to advantage, running a number of delay lines of different lengths in parallel and noting a solution when they all returned input data simultaneously. It also had vacuum-tube components. Input was by means of a paper tape which was prepared by software on an IBM 7094} or a CDC 6400. In the early 1970s the machine was upgraded with an additional six moduli and renamed the DLS-157: these new delays were implemented using shift registers rather than delay lines. The Delay Line Sieve ceased operations in 1975; it is now in the collection of the Computer History Museum.