Number Sieves — Volume 5 — Before the Machines: Carissan, Gérardin, Kraitchik and the Lehmers

5.1 About This Volume

Volumes 2 to 4 built the mathematics: primes, the Sieve of Eratosthenes, and the congruence arithmetic that lets a single modulus throw away a fixed fraction of the candidates for a problem. This volume is the human and documentary history that sits between that mathematics and the machines of Volumes 6 to 8. It begins with the great printed factor tables, which were sieves executed by hand on paper at enormous cost, and with the movable-strip method that number theorists used to combine congruences before any machine existed. It then follows the first attempts to mechanise the strips: an unbuilt English design of 1896, a burst of prototypes in Paris in 1912, and the one early machine that actually worked, Eugène-Olivier Carissan’s hand-cranked machine à congruences of 1919, which was forgotten for seventy years and found in a drawer at an observatory near Bordeaux. The second half is about the family that made sieving into a branch of engineering: Derrick Norman Lehmer, the Berkeley table-maker; his son Derrick Henry “Dick” Lehmer, who built the bicycle-chain and gear machines; and Emma Lehmer, who worked beside both of them for sixty years. The volume ends where the machines begin, and with the lecture Dick Lehmer gave in 1982 when he handed his sieves to a museum.

The sources are, wherever possible, the people themselves: D. N. Lehmer’s own history of factor tables and his 1932 account of the gear machine, D. H. Lehmer’s papers of 1928 and 1934 and his 1973 oral history, and the reconstructions by H. C. Williams, J. O. Shallit and R. F. Lukes, who did most of the modern archival work on the early sieves.

5.2 Tables Before Machines

Every number sieve, mechanical or electronic, is a faster way of doing something that people first did on paper. The oldest paper version is the factor table: a printed list giving, for each number in some range, its smallest prime factor (or a mark saying it is prime). A factor table is the Sieve of Eratosthenes run once, very carefully, over a very long strip of integers, and then typeset so that nobody has to run it again.

D. N. Lehmer, who made the largest table of the kind ever printed, wrote the best short history of them in 1918, in an essay for The Scientific Monthly (D. N. Lehmer, “On the history of the problem of separating a number into its prime factors,” Sci. Monthly 7 (1918) 227–234). He opens with the asymmetry that still drives the whole subject:

“It is so easy to multiply two numbers together, and so hard to find them again when they have been welded into one!”

His survey is worth following because it shows the sieve becoming a production process. Eratosthenes’ method, he notes, “requires no computation, and may be carried out by measurement alone”: write the numbers in a row, strike every second one after 2, every third after 3, and so on, and if the struck numbers are labelled with the prime that struck them rather than erased, the row becomes a factor table. The practical problem was bulk. Writing a million numbers in a row “turns out to be a somewhat tedious undertaking,” so table-makers learned to leave out the multiples of small primes altogether. Johann Rahn’s table of 1659 (to 24,000) and Thomas Brancker’s extension of it to 100,000 dropped the multiples of 2 and 5 by arranging the numbers in rows of ten and omitting whole columns. Later tables went to rows of thirty and dropped multiples of 3 as well, and in that arrangement each prime’s multiples recur in the same column at a fixed spacing, so a single cut-out stencil can mark them all at once. Lehmer credits the stencil method to C. F. Hindenburg in 1776, the same year that Anton Felkel published a table to 408,000 — a table so poorly bought, by Lehmer’s account, that “the entire edition was made into cartridges to use against the Turk.”

The nineteenth century brought the great tables: Ladislaus Chernac’s Cribrum Arithmeticum (1811), whose title is simply “the arithmetic sieve,” to 1,020,000; J. C. Burckhardt’s insight that only the smallest factor need be printed, since the rest follow by division; Burckhardt’s first three millions; J. W. L. Glaisher’s fourth, fifth and sixth; and Zacharias Dase’s seventh, eighth and ninth. In the background lay the unpublished manuscript of the Bohemian computer J. P. Kulik, who had tabulated factors to about 100 million. Lehmer examined Kulik’s tenth million “with great care” against his own work and “found some 226 errors in this one million” — enough to make the manuscript unpublishable, though still valuable for checking.

5.2.1 D. N. Lehmer’s ten million

The table that closed the paper era was Lehmer’s own. The Factor Table for the First Ten Millions, published in 1909 by the Carnegie Institution of Washington, gives the smallest factor of every number not divisible by 2, 3, 5 or 7 up to 10,017,000 (Williams & Shallit, “Factoring integers before computers,” 1994, reference 92). Omitting multiples of 2, 3, 5 and 7 removes about 77 per cent of all integers before any work is done — a wheel sieve (Volume 3) applied to the layout of the page. In 1914 the same institution published Lehmer’s List of Prime Numbers from 1 to 10,006,721, derived from the factor table and reviewed in Nature the following May (Nature 95 (1915) 254). The MacTutor biography quotes the historical preface of the 1909 volume: “From the days of Eratosthenes, the inventor of factor tables, to the present time the interest in the problem has never flagged” (MacTutor, Derrick Norman Lehmer).

The tables mattered to the machines in two ways. They set the boundary below which factoring was a solved problem — “we are complete masters of the situation for numbers up to ten millions,” Lehmer wrote in 1918 — so every problem the later sieves attacked lay beyond it. And they taught a family that a sieve is something you build: a process that rewards careful layout, error checking and the elimination of wasted work.

5.2.2 Factor stencils

A factor table answers “what divides this number?” only for numbers inside its range. For larger numbers the Lehmers built a different paper machine. Its principle, as Dick Lehmer later put it, is that “every quadratic residue R of a number N is also a quadratic residue of every possible factor of N,” so finding a handful of small quadratic residues of N confines its prime factors to a short list (MacTutor, Derrick Norman Lehmer). Each residue R corresponds to a card punched with a hole at every prime (among the first 5,000) that has R as a quadratic residue. Stack the cards for the residues you know, and only the primes that are holes in every card remain visible.

The Factor Stencils were published by the Carnegie Institution in 1929. According to Williams and Shallit, each stencil was a grid of 100 rows by 50 columns, one cell per prime of the first 5,000 (D. N. Lehmer counted 1 as a prime, so his 5,000 ended at 48,593), about 20 cm by 43 cm, supplied in a wooden box with a glass cover; an electric light inside the box shone through the stacked stencils (Williams & Shallit 1994, pp. 505–506). MacTutor gives the residues as those below 240 and the prime limit as 48,611; the two accounts differ in detail and the original volume was not consulted for this series. In 1939 J. D. Elder transferred the stencils to 2,000 Hollerith cards. The Computer Museum’s 1983 report on the Lehmer exhibit records that “a great deal of kitchen-table work was performed by the whole Lehmer family in order to create these cardboard pieces” (R. Rubinstein, “D. H. Lehmer’s Number Sieves,” The Computer Museum Report, Spring 1983, p. 3).

The factor stencils are already a sieve in every sense that matters: the candidates (primes) are laid out in a fixed order, each modulus-condition is a pre-cut pattern, and the survivors are those positions where every pattern is open — exactly the holes-in-gears principle of the 1932 machine, read with a lamp.

5.3 The Strip Method

The stencils sieve a fixed list of primes. The harder problem, and the one the machines were built for, is to combine many congruence conditions on an unknown x — “x must be 2, 3, 4, 8, 9 or 10 modulo 11; x must be one of these values modulo 13; …” — and find the smallest x that satisfies all of them. Volume 4 shows how such conditions arise from factoring by differences of squares; here the question is how they were combined before machines.

The answer was the movable strip. D. H. Lehmer described it in 1928, crediting Maurice Kraitchik’s Théorie des Nombres of 1922: “use is made of a table ruled in squares, each cell representing a possible value of a. ‘Movable strips’ are made, the length of each being some excluding number p, and on which impossible values of a modulo p are indicated by crosses. These strips are moved down the columns of the table and the cells adjacent to the crosses on the strip are then ruled out” (D. H. Lehmer, “The mechanical combination of linear forms,” Amer. Math. Monthly 35 (1928) 114–121, p. 114). After enough strips, only a few cells remain empty, and those few candidates are tested by hand.

Lehmer listed the method’s faults precisely, and they are the design requirements of everything that followed. It “requires very close attention and much care.” The strips “are short in comparison with the length of the table and have to be shifted frequently, which is a possible source of error.” Worst, “the method makes it necessary to fix the limit of the table before commencing the work, so that the whole range must be entirely covered before any definite information can be obtained” (LF28, p. 115). A table with a fixed edge cannot stop early on a small answer and cannot be extended without being redrawn. The scale of the hand work is visible in Lehmer’s note on Kraitchik’s search for pseudosquares: Kraitchik “used the movable strip method with a table having 180 columns and 84 lines” (LF28, p. 121).

A machine that presents the candidates one at a time, in order, fixes all three faults at once. Nothing needs to be shifted by hand, there is no upper limit to fix in advance, and the first survivor appears as soon as it is reached. Lehmer made the point again in 1934: the one-at-a-time method “seems, at first sight, to be very crude,” but “no mention need be made of the upper limit L” (D. H. Lehmer, “A machine for combining sets of linear congruences,” Math. Annalen 109 (1934) 661–667, p. 662).

5.4 Lawrence’s Unbuilt Machine (1896)

The first description of a sieving machine came from England. F. W. Lawrence, writing on factorisation in the Quarterly Journal of Mathematics in 1896, first described paper strips and then proposed something better: a gear of m teeth for each excluding modulus m, every gear with the same tooth size and driven by one common driving gear, the teeth numbered 0 to m − 1, and “a brass stud would penetrate through it at the point(s) of an acceptable (mod m) residue.” When studs from every gear were in contact at once, “a circuit would be completed and a bell would ring or the machine would stop” (Williams & Shallit 1994, pp. 511–512). Lukes adds the geometry: because gears of different tooth counts have different diameters, each needed its own axle, and Lawrence fanned the gears out so they were close together at the driving gear and the studs could touch there (R. F. Lukes, A Very Fast Electronic Number Sieve, PhD thesis, University of Manitoba, 1995, pp. 10–11).

Lawrence never built it. His sketch nonetheless contains every element of D. H. Lehmer’s 1932 gear sieve except the light: one gear per modulus, equal tooth pitch so that every gear advances one residue per step, a common driver, a mark at each acceptable residue, and an electrical coincidence detector that stops the drive.

5.5 Paris, 1912: Gérardin, Kraitchik and the Carissans

Lawrence’s paper might have stayed a curiosity but for André Gérardin, who in 1910 published a French translation of it in his own small mathematical periodical, Sphinx-Oedipe. Williams and Shallit call it his “peculiar journal/newsletter,” and describe the effect: “a flurry of activity, apparently inspired by Andre Gérardin, began to produce some results” (Williams & Shallit 1994, p. 512).

Maurice Kraitchik announced the first machine, in Sphinx-Oedipe in February 1912. Kraitchik (1882–1957), born in Minsk and later a Belgian engineer and populariser of mathematics, is best known to number theorists for his books Théorie des Nombres (1922) and Recherches sur la théorie des nombres (1924) and for editing the recreational periodical Sphinx from 1931 to 1939 (Wikipedia, “Maurice Kraitchik”). His machine, built of wood, was “rather similar to that of Lawrence, except that the gears representing the various exclusion moduli are each mounted on the same shaft. Also, he mentions the possibility of putting holes in the gears (instead of studs) and shining light through onto a screen” (Williams & Shallit 1994, p. 512). Lukes, working from the April 1912 description, gives more: fifteen modulus gears turning freely on one shaft, each meshed with one of fifteen 64-tooth gears fixed to a second shaft, the radii chosen so that every modulus gear advanced one tooth per step; a numbered hole at a fixed 60 mm radius beneath each tooth; unacceptable residues plugged; a lamp at one end and a screen at the other, on which “a spot of light” signalled a solution (Lukes 1995, pp. 11–12). (The list of Kraitchik’s fifteen moduli in the scanned thesis is too garbled by optical character recognition to reproduce here.) Lukes judged that the machine “probably worked reasonably well at low speeds” but “would very likely have been useless at high speeds because the gear teeth, being of different sizes, would produce meshing problems,” and Kraitchik seems to have abandoned it soon after building it.

André Gérardin reported in March 1912 that he had built a machine of his own, and that Pierre Carissan had designed one. Gérardin’s descriptions of his own devices are, in Lukes’s word, “vague.” The best reading is that his 1912 mechanism used strips, probably of paper, each marked off in a multiple of m equal spaces coloured white or black according to whether the residue was acceptable; the strips, usually about three metres long and nearly equal in length, were wound between two rollers, and an operator watched for a column that was white on every strip (Lukes 1995, p. 12). It is the movable-strip table turned into a scroll.

Pierre Carissan’s machine was built by his brother Eugène-Olivier. Carissan’s own later paper describes it as “hanging, flexible modular loops (rings) which were driven simultaneously by a grooved roller and scanned for solutions by eye,” and admits that it was inefficient (Lukes 1995, p. 12). Hanging flexible loops driven from one roller at the top is, mechanically, the bicycle-chain sieve that D. H. Lehmer would build fifteen years later without knowing of it.

The verdict of Shallit, Williams and Morain on all three 1912 efforts is blunt: they “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” (quoted in Wikipedia, “Lehmer sieve”; Lukes gives the same judgement in nearly the same words, p. 13). The weakness they share is the last of those: a person’s eye was the coincidence detector. A sieve that has to be watched cannot run faster than a watcher can see, and cannot run unattended.

5.6 Carissan’s Congruence Machine (1919)

5.6.1 The machine

Eugène-Olivier Carissan, a lieutenant in the French infantry, started again in 1913–14 with a new prototype, and was encouraged enough to order a precision version from the Paris firm of Chateau Frères. The First World War intervened, and the machine was not finished until 1919 (Lukes 1995, p. 13; Williams & Shallit 1994, p. 512). Williams and Shallit’s assessment is that “this seems to have been the first automatic sieve mechanism to have ever been successfully constructed.”

The design, as reconstructed from Carissan’s detailed 1920 paper in the Bulletin de la Société d’Encouragement pour l’Industrie Nationale (vol. 132, pp. 600–607), is a flat instrument rather than a frame of loops:

• Fourteen concentric brass rings, one for each of the moduli 19, 21, 23, 26, 29, 31, 34, 37, 41, 43, 47, 53, 55 and 59.
• A pinion gear whose axis lies parallel to the plane of the rings drives all fourteen at the same linear rate.
• Each ring carries m equally spaced studs on its upper face, the spacing being the same on every ring, so one step of the drive advances every ring by one residue.
• Studs at acceptable residues are fitted with non-conducting caps.
• An arm over the rings carries a contact for each ring along a radial “line of investigation.” The contacts are in series, and when every stud under the arm is capped, the circuit completes and a sound is produced in a telephone receiver held at the operator’s ear.
• The drive is hand-cranked, at 35 to 40 numbers a second, and a counter (to 1,000,000; Lukes says six digits) records the step.

(Williams & Shallit 1994, pp. 512–513; Lukes 1995, p. 13.)

The choice of moduli is revealing. None of the fourteen is a small prime: 21 = 3·7, 26 = 2·13, 34 = 2·17 and 55 = 5·11 carry two small primes on one ring each, and the primes from 19 to 59 have rings of their own. A ring for 2 or 3 would have been tiny and, at a fixed stud spacing, useless; Lehmer met the same problem with short chains and solved it the other way, with prime-power chains of 64, 27, 25 and 49 links (Volume 6).

The capped-stud detector is the decisive improvement over 1912. The operator no longer looked for a pattern; the machine told him, through an earpiece, when every ring agreed. Williams and Shallit report that the machine “required only 15 minutes to prove that M₃₁ is a prime” (p. 513). Other accounts give different worked examples — proving 1,321,442,641 prime in 15 minutes and 18,405,321,661 prime in an hour (Wikipedia, “Lehmer sieve”, citing the 1995 Mathematical Intelligencer paper, which was not available to this series); the two may describe different problems, and the figures are reported here as published.

Carissan regarded the 1919 instrument as a first model. An unpublished manuscript of May 1920 lists four improvements for later versions, among them driving the machine with an electric motor (Lukes 1995, p. 13). None was made. Pierre Carissan died in 1923 and Eugène-Olivier in 1925, and the paper describing the machine had appeared in a journal few mathematicians read.

5.6.2 Lost and found

The machine spent roughly fifty years in a drawer at the Observatoire de Bordeaux in Floirac. Jeffrey Shallit, Hugh Williams and François Morain, alerted by Carissan’s relatives Marie-Josèphe Salefran-Carissan and France Silber, inspected it there several times; Silber, a daughter of E.-O. Carissan, then took possession of it and gave it to the Conservatoire National des Arts et Métiers in Paris. The three published the story as “Discovery of a lost factoring machine” in The Mathematical Intelligencer 17(3) (1995) 41–47, with a French version in La Revue of the Musée des Arts et Métiers in 1996 (Shallit, Williams & Morain, project page; Williams & Shallit 1994, p. 513; doi:10.1007/BF03024369). Lukes, writing in the same year, called it “the earliest example extant, of a special purpose automatic mechanism for solving number theoretic problems.”

D. H. Lehmer did not know it existed. Williams and Shallit record that he “was unaware of the work of the Carissans and remained so until 1989” (p. 513). In 1934 Lehmer had written, of earlier sieve machines, that “the literature contains at least two descriptions of such machines which, though impractical in their design, are theoretically interesting. As far as the writer knows, the first successful machine of this type was constructed by him in 1927” (LMC34, p. 663). The two descriptions were Lawrence’s and Kraitchik’s. Williams and Shallit thought it “rather strange that he gives so very little credit to them, especially since his photoelectric sieve of 1932 represents in many ways the fruition of their ideas,” and explain the silence: Lehmer “had determined that neither of these earlier mechanisms, as described, would actually work.”

5.6.3 Gérardin’s later machine

Gérardin did not give up. In 1937 he described a new machine à congruences to the French Association for the Advancement of Science, “apparently totally unaware of Lehmer’s previous work.” A photograph suggests it was built on an adding machine; Lukes reports that it was “electric, automatic, able to print” and ran “at the rate of about 25000 operations per working day” (Lukes 1995, p. 16). By then Lehmer’s gear sieve had been running at 5,000 candidates a second for five years.

5.7 Kraitchik and the Lehmers: Rivals at the Same Table

Kraitchik matters to this story less for his 1912 machine than for his tables and his methods. His Théorie des Nombres (vol. 1, 1922; vol. 2, 1926) printed, for every excluding prime up to 47 (later 67), the possible values of a modulo p for the difference-of-squares problem — exactly the “pin positions” a sieve operator needs. When D. H. Lehmer set up his chain machine he used Kraitchik’s tables, recalculated them, extended them to 67 for the machine’s longest chain, and printed a list of errors at the end of his 1928 paper, adding a note that Kraitchik’s second volume had since corrected them (LF28, pp. 117 and 121). His very first published sieve result after the factorisations was an extension of a Kraitchik problem: the least non-square that is a quadratic residue of every prime up to p, which Kraitchik had carried by hand to p = 47 and the chain machine carried to p = 61 (LF28, p. 121). Those numbers — later called pseudosquares — run through the rest of the series to the electronic sieves of Volume 8.

The two men’s paths crossed most dramatically over the Mersenne number M₂₅₇ = 2²⁵⁷ − 1, the last unsettled entry on Mersenne’s list. Williams and Shallit tell the story from Lehmer’s journals. Kraitchik claimed in 1926 that he had shown M₂₅₇ composite in 1922, after five months’ work, but gave no details. In June 1926, unaware of the claim, Dick Lehmer began the same computation with a ten-digit desk calculator, checking each step modulo 1001, and finished on 6 March 1927 — only to find later that one term was wrong and all the work since August 1926 was void. When Lehmer asked for Kraitchik’s computations, Kraitchik said he had sent them to Gérardin, who replied that “owing to the state of his health, he could not at that time recover Kraitchik’s calculations from among the thousands of kilograms of archives in his possession.” When Lehmer later visited Gérardin’s office he found it “full of papers piled up everywhere and in no apparent filing system.” It was Emma Lehmer who found the error; from 1930 the couple redid the calculation together, checking modulo 10⁸ + 1 and 10⁹ + 1, and Lehmer announced in June 1932 that M₂₅₇ is composite — work estimated at over 700 hours (Williams & Shallit 1994, pp. 516–517).

5.8 Derrick Norman Lehmer (1867–1938)

Derrick Norman Lehmer was born on 27 July 1867 in Somerset, Indiana, and grew up in Nebraska. He took his A.B. at the University of Nebraska in 1893, worked as a railroad surveyor, returned for a master’s degree in 1896, and earned his Ph.D. at the University of Chicago in 1900 under E. H. Moore with a thesis on Asymptotic Evaluation of Certain Totient-Sums. He was appointed instructor at the University of California, Berkeley, that same year, became professor in 1918, retired on 27 July 1937, and died at home in Berkeley on 8 September 1938. He and Clara Eunice Mitchell, a poet, married in 1900 and had five children, of whom Derrick Henry, born in 1905, was the third (MacTutor, Derrick Norman Lehmer; Huskey, “Derrick Henry Lehmer,” IEEE Computer Society Computer Pioneers).

He was a table-maker by vocation — his son said in 1973, “my father was an old table-maker himself” (D. H. Lehmer, oral history interview by R. Mapstone, 18 April 1973, Smithsonian/AFIPS Computer Oral History Collection, p. 14) — and he was at one time Research Assistant of the Carnegie Institution of Washington, which published the factor table. He was also a composer and poet: Berkeley’s obituary spoke of “the Derrick strain” that made him a mathematician and “the Norman strain” that produced operas, songs and poems, among them The Harvest, performed in San Francisco in October 1933, and The Necklace of the Sun, premiered in Oakland in 1935 (MacTutor).

D. N. Lehmer was the grant-holder and public voice of the gear sieve. MacTutor quotes a contemporary report that the Carnegie Institution had made “the grant of $1,000 to Dr Derrick N Lehmer of the Mathematics Department of the University of California” for a machine “to be constructed under Professor Lehmer’s direction by his son Derrick H Lehmer, national research fellow.” The report’s description — “a shaft on which thirty gears of 100 teeth each are set,” meshing with “thirty other gears with a varying number of teeth, depending on the prime numbers from 1 to 127,” a hole under each tooth, a beam of light and a photo-electric plate — is a plan rather than an as-built account (Volume 7 compares it with the machine), but it fixes the father’s role. His essay “Hunting big game in the theory of numbers” (Scripta Mathematica, 1932) is the liveliest description of the gear machine at work, written by a parent who admits to being “in something of a state of nerves” while the machine searched (transcription at ed-thelen.org). Volume 7 quotes it at length.

5.9 Derrick Henry “Dick” Lehmer (1905–1991)

5.9.1 Berkeley, Chicago, Brown

Derrick Henry Lehmer, always “Dick,” was born in Berkeley on 23 February 1905 and grew up inside his father’s work. MacTutor notes that the Factor Table appeared when he was four and the List of Prime Numbers when he was nine (MacTutor, Derrick Henry Lehmer). He entered Berkeley in 1923 and studied physics while helping his father with computations and with the factor stencils. The record is inconsistent about the degree: Huskey gives an A.B. in mathematics in 1927, MacTutor a B.A. in physics in 1927, and Lehmer himself, in 1973, said “I got a degree in physics in 1928” (oral history, p. 1). The weight of evidence is 1927.

It was as an undergraduate that he built the bicycle-chain sieve. His own words in 1973: “Before I left Berkeley even, I had built an automatic sieve — you might say an electro-mechanical sieve, in 1927.” Asked why, he described the strip method: “one got a big piece of paper and a strip of paper that you applied successively to positions on the paper and you just sort of crossed out … The thing was to do this mechanically, of course. Electro-mechanically … So I built this machine in Berkeley as an undergraduate” (oral history, pp. 1–2). Other sources date the machine to 1926 (Huskey; the Computer Museum; M. R. Williams, who places it in the students’ shop in LeConte Hall). Volume 6 is devoted to it.

He spent 1927–28 at the University of Chicago working with L. E. Dickson, was unhappy there, and moved to Brown University in Providence, Rhode Island, as an instructor, taking a master’s degree in 1929 and a Ph.D. in 1930 with a thesis on An Extended Theory of Lucas’ Functions, supervised nominally by J. D. Tamarkin — Huskey says the work was “essentially unsupervised since no one at Brown was interested in number theory” (Huskey). The Lucas–Lehmer test for Mersenne primes, which every modern record prime still passes through, comes from this period. Before the move east he dismantled the chain sieve, and it was stolen before it could be rebuilt (Lukes 1995, p. 14).

5.9.2 Fellowships and the gear machine

The Great Depression made the next years itinerant: a National Research Council fellowship at the California Institute of Technology (1930–31, with E. T. Bell) and at Stanford (1931–32, with J. V. Uspensky); a year at the new Institute for Advanced Study in Princeton (1933–34); and then Lehigh University in Pennsylvania from 1934 to 1940, with a Guggenheim year in Cambridge and Manchester in 1938–39 (Huskey; MacTutor). The photoelectric sieve was designed at Brown and built during the fellowship years: “part of my postdoctoral work was to build this photo-electric sieve which I built myself partly and with the help of R.C. Burt Engineering in Pasadena who did the electronics on it. I did the mechanical part. And it all came together in 1932 here” (oral history, p. 2). The machine travelled with him — to Chicago, to Princeton, and back to Berkeley, “and it is still here,” he said in 1973. Volume 7 covers it.

5.9.3 ENIAC, SWAC and the loyalty oath

Lehmer returned to Berkeley in 1940. In 1945–46 he was at the Ballistic Research Laboratory at Aberdeen Proving Ground, on the small committee planning computation for the ENIAC; by his own account he was “put in charge of the ENIAC about January, I guess, of 1946” (oral history, p. 3). Over a holiday weekend the Lehmers turned the ENIAC into a sieve. Huskey quotes Lehmer’s 1980 recollection: “We had a Fourth of July weekend situation when the Lehmer family was allowed to come in and pull everything off the machine and reset the ENIAC for our particular problem. The Lehmer family consisted of myself, my wife, and two teenage kids” — and it was John Mauchly “who suggested that we ought to use some of the arithmetic units to make a kind of sieve,” worked out “in a restaurant just before we went to work” (Huskey). Software sieves followed on the SWAC and the IBM 7094; Volume 8 takes them up.

In 1950 the University of California required its staff to sign a loyalty oath. Lehmer refused — “I decided that I would not sign and so I walked out, so to speak. They didn’t fire me, but I just refused to sign” — and became director of the National Bureau of Standards’ Institute for Numerical Analysis at UCLA for 1951–52, where the SWAC was being brought into service (oral history, pp. 5–8). Huskey records the SWAC’s most famous number-theoretic night from that period: Raphael Robinson mailed a Lucas–Lehmer test program from Berkeley, it ran without error, and on its first evening found the Mersenne primes 2⁵²¹ − 1 and 2⁶⁰⁷ − 1. Lehmer returned to Berkeley in 1954 when the oath was dropped, chaired the mathematics department from 1954 to 1957, retired in 1972, and died in Berkeley on 22 May 1991 (Huskey).

Robert Silverman’s announcement of his death to the numerical-analysis community called him “the father of computational number theory” (NA Digest, 23 May 1991, quoted at ed-thelen.org). His Selected Papers (1981) include a whole section on sieves.

5.10 Emma Lehmer (1906–2007)

Emma Markovna Trotskaia was born on 6 November 1906 in Samara on the Volga. Her father represented a Russian sugar company and moved the family to Harbin in Manchuria when she was a small child; she was tutored at home until a community school opened when she was fourteen. Unable to return to Russia after the Revolution, she saved money from translating, babysitting and coaching, and came to Berkeley in 1924 to study engineering, switching after two years to mathematics. Her favourite teacher was D. N. Lehmer, and “as well as taking several of his courses she did a research project with him on finding pseudosquares” — the very problem the chain machine extended in 1928 (MacTutor, Emma Lehmer). She graduated with honours in 1928 and married Dick Lehmer the same year. At Brown she took a master’s degree in 1930.

She never took a doctorate and later wrote an essay “On the advantages of not having a Ph.D.”: “First of all there are lower expectations. If one happens to discover something new, one’s peers are pleasantly surprised and generous in their praise.” Rules against husband and wife teaching in the same department kept her off the faculty, which she counted as more time for research. MacTutor credits her with around sixty papers, about twenty of them joint with her husband; Wikipedia gives 56 and 21 (MacTutor; Wikipedia, “Emma Lehmer”). She translated Pontryagin’s Topological Groups into English (1939), worked on reciprocity laws and cyclotomy, and with her husband founded the West Coast Number Theory conference in 1969. She died in Berkeley on 7 May 2007, aged 100.

Her role in the machines is easy to under-state because the papers carry her husband’s name. MacTutor quotes a joint application to the Carnegie Institution around 1930 for funds to build a factoring machine: “To perform the operation with pencil and paper one must start with the million or so numbers among which the solution is known to lie. Actually to write out all these numbers is obviously impossible. We therefore propose to construct a machine which will canvass a million numbers in about three minutes” (MacTutor, Emma Lehmer). A million numbers in three minutes is 5,500 a second — almost exactly what the gear sieve achieved. She caught the error in the M₂₅₇ computation, worked the ENIAC sieve weekends of 1946 (“when they could arrange child care, they often stayed at the lab all night long”), and in the 1960s co-authored the Delay Line Sieve’s principal published results (D. H. Lehmer, E. Lehmer & D. Shanks, “Integer sequences having prescribed quadratic character,” Math. Comp. 24 (1970) 433–451). Harry Huskey remembered calling at the delay-line sieve’s room in Cory Hall: if the machine had stopped on a hit, “there was a flurry of activity as Emma or Dick copied down the ‘hit’ number and did some auxiliary computation” (Huskey).

5.11 The 1982 Lecture

On 7 October 1982 D. H. Lehmer opened the fall lecture series of The Computer Museum in Boston and dedicated its exhibit of his sieves: the photoelectric gear machine, the 16 mm film sieve, the delay-line sieve, his father’s factor stencils, and a working reproduction of the bicycle-chain sieve then being built by Roberto Canepa, Andrew Kristoffy and Richard Rubinstein (Rubinstein 1983, pp. 1–4). The museum’s report notes that Scientific American sent a photographer to shoot the machines for its November issue; Lukes cites Carl Pomerance’s article “The search for prime numbers” (Scientific American 247, 1982) for the chain-sieve reproduction. The videotape, catalogued by the Computer History Museum as The History of the Sieve Machine and dated 6 October 1982, survives (CHM catalogue 102639706), and a copy is on YouTube (D. H. Lehmer, 1982 lecture). The recording was not reviewed for this series; kbsriram, who built the electronic sieve described in Volume 8, quotes it for the design of Lehmer’s last sieve — a bank of read-only memories and counters, one pair per modulus, on a shared clock — and for Lehmer’s case for an “adjustable sieve”: “we don’t have to commit ourselves hardware wise to the set of modulus that we use” (kbsriram, A Tiny Sieve, build log 6). The museum’s report also notes that Lehmer was “now working with his grandson on a new machine using integrated circuit technology” (Rubinstein 1983, p. 3).

Two years earlier Lehmer had written the history of the subject himself, “A history of the sieve process,” in A History of Computing in the Twentieth Century (Academic Press, 1980, pp. 445–456; doi:10.1016/B978-0-12-491650-0.50030-7). The volume was not available to this series and is known here through quotations by Huskey and by Williams and Shallit. One line from it is the fairest summary of where the field stood: “It’s very esoteric, of course, and since I am practically the only man working in this field you can see how widespread the interest in it is” (quoted in Williams & Shallit 1994, p. 514).

5.12 What Carried Forward

Laid side by side, the pre-1926 devices already contain every idea the Lehmer machines used, and the difference is engineering rather than concept:

Table 1 — Laid side by side, the pre-1926 devices already contain every idea the Lehmer machines used, and the difference is engineering rather than concept

Idea	First appearance	In the Lehmer machines
One periodic element per modulus	Strip method; Lawrence 1896	Chains (1927), gears (1932), film loops (1936), delay lines (1965)
Small primes folded into prime powers or products	Carissan’s rings of 21, 26, 34, 55	Chains of 64, 27, 25, 49, 22, 26
Common drive so every element steps together	Lawrence; Kraitchik; Carissan’s pinion	One shaft of sprockets; one driving gear train
Holes and light	Kraitchik 1912 (onto a screen)	Photocell and amplifier, 1932
Electrical coincidence detection	Lawrence (bell); Carissan (series contacts, telephone)	Springs and relay, 1927; photocell, 1932; AND gate, 1965
Unattended running and automatic stop	Lawrence (proposed)	Every Lehmer machine
Counter giving the candidate	Carissan’s six-figure counter	Revolution counters; later electronic counters

What the Lehmers added was speed, reliability and the motor — and with the motor, the ability to leave a machine running overnight on a problem whose range had no fixed end. The next volume takes apart the first of their machines, the frame of bicycle chains that Dick Lehmer built as a Berkeley undergraduate.

---

Next — Volume 6: The Bicycle-Chain Sieve (1926–1928). Nineteen loops of chain on one shaft, pins of chicken wire, springs with tungsten points on a brass bar, and a revolution counter: the machine that factored 9,999,000,099,990,001 in two hours, described closely enough to rebuild — including two stops its inventor never reported.