Number Sieves — Volume 14 — Running Lehmer's Problems: Test Protocol and Results

14.1 About This Volume

A reproduction is proved by running the original’s problems and getting the original’s answers. This volume collects the six problems that D. H. Lehmer published from his 1928 chain machine and his 1932 gear machine and that kbsriram reran on his ATtiny sieve in 2026; gives each one’s setup on each of the three builds in Volumes 11, 12 and 13; predicts, exactly, where each machine must stop and how long it should take; and lays out a protocol and a results sheet for recording the runs.

The predictions are not estimates. Because the acceptable residues for every modulus are fixed by the problem, the complete list of steps on which a machine with a given set of moduli will stop can be computed in advance — and it has been, for every problem and every machine, by 03-outputs/cad/lehmer_runs.py. A machine that stops anywhere else, or fails to stop where it should, is wrong, and the list says where to look.

The results columns for the builds are empty. They are for the builds’ own runs.

14.2 The Six Problems

kbsriram’s final build log, “The modulus chorus plays for us”, reruns six problems from three papers:

• LF28 — D. H. Lehmer, “The Mechanical Combination of Linear Forms,” American Mathematical Monthly 35 (1928), pp. 114–121 (copy): the chain machine.
• PS33 — D. H. Lehmer, “A Photo-Electric Number Sieve,” American Mathematical Monthly 40 (1933), pp. 401–406, doi:10.1080/00029890.1933.11987465: the gear machine. (Not read for this series; figures attributed to it here come through kbsriram.)
• NF33 — D. H. Lehmer, “Some New Factorizations of 2ⁿ ± 1,” Bulletin of the AMS 39 (1933), pp. 105–108 (AMS): the gear machine’s first month of results.

He set his step clock to each machine’s own speed — 50 candidates a second for the chain problems, using 19 cards to match the 19 chains, and 5,000 a second for the gear problems, using all 30. His table:

Table 1 — He set his step clock to each machine's own speed — 50 candidates a second for the chain problems, using 19 cards to match the 19 chains, and 5,000 a second for the gear problems, using all 30. His table

Problem	Paper	Rate	Published	kbsriram’s sieve	Stops
9,999,000,099,990,001	LF28	50/s	”about 2 hours”	2 h 14 min 09 s	2
a factor of 3¹¹¹ + 1	LF28	50/s	”only 4 seconds”	2.96 s	1
4,500,383,424,373 as a sum of two squares, run 1	LF28	50/s	”one stop, not a solution”	1 h 05 min 42 s	1
the same, run 2	LF28	50/s	”stopped only once”	52 min 37 s	2
2⁷⁹ − 1	PS33	5,000/s	”12 s”	11.31 s	1
2⁹³ + 1	NF33	5,000/s	”a few seconds”	1.41 s	1

“Every solution matched the published one,” he writes, and his measured times land within about half a per cent of the step count divided by the clock rate; the shortfall is the board’s periodic self-test checkpoints and display updates. The run-1 time is the time to its one (false) stop; the run then exhausted its range.

The problems, briefly — each driver in code/06/rpi/slower/ of kbsriram’s repository documents its problem in full, and Volume 9 works the mathematics.

14.2.1 9,999,000,099,990,001 (LF28 pp. 115–118)

N = (10²⁰ + 1)/(10⁴ + 1) was known to be the product of two primes. From the quadratic characters of 3 and 7 Lehmer derived that a factor-revealing a in N = a² − b² must be a = 7200x + 100,000,601, with 0 ≤ x < 5,772,578. He restricted the 49-link chain by hand to eight residues (x ≡ 2, 9, 16, 23, 25, 30, 37, 44 mod 49) instead of the 28 a plain test allows. The machine “stopped itself at x = 400453” after about two hours: a = 2,983,262,201, b = 2,981,585,880, N = 1,676,321 × 5,964,848,081. Because the step 7,200 = 2⁵ · 3² · 5² already absorbs the factors of 2 and 5, the 64- and 25-link chains accept every residue on this problem — “Lehmer would have pinned every link on both these chains,” as kbsriram puts it.

14.2.2 A factor of 3¹¹¹ + 1 (LF28 pp. 118–119)

The cofactor M = 2,019,210,335,106,439 — printed in the paper with one digit too many, as kbsriram notes; the published factors confirm the correct value — has every factor of the form 111n + 1. Lehmer’s equation (5) gives a = 49,284x + 44,978,200 with 0 < x < 203,943, and two moduli need special treatment because they share factors with the step 49,284 = 2² · 3² · 37²: the 27-link chain is worked modulo 9 (x ≡ 1, 4, 7, 8), and the 37-link chain uses the form reduced by 37². The machine stopped “after running only 4 seconds” at x = 145: M = 25,709,599 × 78,539,161. (The paper’s earlier statement that a ≡ 2 mod 4 contradicts its own equation (5) and the published answer; kbsriram documents the conflict in prob_f111.py.)

14.2.3 4,500,383,424,373 as a sum of two squares (LF28 pp. 119–120)

From the Pell equation X² − 1721y² = −1 Lehmer obtained y = 17 × 4,500,383,424,373, every factor of which is a sum of two squares. Using 5 as an excluding number he split the search into two runs, a = 5x + 2 and a = 5x + 3, each over 0 ≤ x < 300,013. Run 1 stopped once, at x = 196,113, on a number “not a square although it is a residue of every prime ≤ 67” — the only false stop the paper reports. For run 2 he moved no pins: he set every chain to start on the link for 1/5 mod p. It “stopped only once,” at x = 157,044: N = 785,223² + 1,970,738², a unique representation, so N is prime.

14.2.4 2⁷⁹ − 1 (PS33)

The gear machine’s showpiece: 2⁷⁹ − 1 = 2,687 × 202,029,703 × 1,113,491,139,767, published as found in 12 seconds. kbsriram’s driver uses the quadratic and range attributed to PS33, Q(x) = 91,894,770,302,976x² + 287,722,528,867,021,824x + 256,527,596,541,064,768 with 0 ≤ x ≤ 39,110,012, and the stop at x = 56,523 — 11.3 seconds at 5,000 a second. NF33 describes the same factorisation split into eight runs, the third of which “stopped almost at once” at x = 58,088 under a different parametrisation (Volume 7); the reproduction follows kbsriram’s form so its result can be compared with his.

14.2.5 2⁹³ + 1 (NF33; also Math. Annalen 109, 1934)

The cofactor N = 1,537,228,672,093,301,419 of 2⁹³ + 1, with its smallest factor known to exceed 300,000. Lehmer’s 1934 paper sets it up in full: a = 69,192x + 1,239,854,518 with 0 ≤ x ≤ 37,010,176. The gear machine “stopped in about 3 seconds at x = 6886” — the first real work it did, on 9 October 1932, according to D. N. Lehmer — giving N = 529,510,939 × 2,903,110,321. The step 69,192 = 2³ · 3² · 31² shares factors with 27 and 31, so those gears use reduced forms; kbsriram’s prob_n93.py explains why.

14.2.6 A seventh, for the gear machine: 5,283,065,753,709,209

Not in kbsriram’s six, but the number factored at the gear machine’s first public demonstration in October 1932, and the one his build 02 attacked with three moduli: M = 5,283,065,753,709,209 written twice as x² + 7y² with y = 4k, 0 ≤ k ≤ 6,868,058. The two representations come at k = 2,694,907 and k = 5,676,028, and gcd(M, x₁y₂ + x₂y₁) = 59,957, so M = 59,957 × 88,114,244,437. It is the hardest of the seven for a slow machine — 5.7 million steps to the second representation — and the best demonstration of why the gear machine needed thirty moduli.

14.3 Errors and Omissions in the Papers

Reproducing a published computation is a test of the publication as well as the machine. kbsriram found, and this series has independently checked with lehmer_runs.py:

• Two unreported stops on the chain machine. On 9,999,000,099,990,001, a machine with Lehmer’s nineteen chains stops first at x = 257,749 (a = 1,955,793,401; a² − N is not a square), 48 minutes before the published stop. On the second sum-of-squares run it stops at x = 102,151 (N − a² = 4,239,509,689,809, not a square) before the answer, so it “stopped only once” is not what nineteen chains would do. Both values are quadratic residues of every prime up to 67 and squares modulo 64, 27 and 49; the smallest prime that rejects either is 73. The machine as described could not have rejected them. Most likely they were simply not mentioned; the paper does not say.
• Two misprinted numbers. M for 3¹¹¹ + 1 is printed as 20,191,210,335,106,439 on pp. 118 and 119, and the Pell solution X as 31,738,680,901,536,260 on p. 119; each has one digit too many.
• A contradiction about a mod 4 in the 3¹¹¹ + 1 setup (above).
• The gear machine’s period. kbsriram reports that PS33 gives the period — the count of steps before every gear returns to its starting tooth — as 2,497,194,316,592,991,015,263,471,297,031,949,336,968,700,272,210, which is exactly the product of the first thirty primes with 79 counted twice. With the moduli he uses (64, 27, 25, 49 and the primes 11–113) the true period is about 128 times larger. The surviving machine’s labels (128, 81, 25, 121 …) and Lehmer’s 1934 description (gears of 67 to 128 teeth) suggest still different tooth counts (Volume 12); the true period of the original gear train cannot be computed until the tooth counts are known.

None of these touches an answer. All of them are the kind of thing only a reproduction finds.

14.4 How Each Build Runs Each Problem

14.4.1 The chain sieve (Volume 11)

The chain sieve takes the 1928 problems natively. Load each with chain_tabs.py (presets n9999, f111, sos1, sos2), which applies Lehmer’s restricted set for the 49-link chain on 9,999,000,099,990,001 and his modulo-9 and reduced-37 forms on 3¹¹¹ + 1. For run 2 of the sum of squares, do what Lehmer did: leave every tab where run 1 put it and set each chain to start on the link for 1/5 mod p instead of its red link. (chain_tabs.py builds run 2’s sets directly; kbsriram verified that they are run 1’s sets shifted by −1/5 mod p for every chain except 25, where 5 has no inverse and the chain accepts everything in both runs.)

The gear problems can also be run on the chain sieve, with the nineteen chain moduli in place of the thirty gear moduli. They are slow — 2⁷⁹ − 1 is 56,523 steps — but they are a good long test. The rings are built the same way (lehmer_runs.py computes them for any set of moduli).

The staged eight-chain machine stops far more often. It is practical only with the controller checking every stop automatically (Volume 11, “The controller”), and even then only on short problems. The factor of 3¹¹¹ + 1 is its natural first real problem: its first stop is the answer.

14.4.2 The gear sieve (Volume 12)

The gear sieve takes the 1932 problems natively, with each gear plugged from the ring for its modulus: the 128-tooth gear for modulus 64, the 81-tooth for 27, the 75-tooth for 25, the 98-tooth for 49, the 121-tooth for 11, and so on — each residue’s pattern repeated round the gear as many times as the modulus divides the tooth count. gear_sieve_gears.py --modulus m --teeth N --open … draws the plug map for each gear from the residue list.

The 1928 problems run on the gear set too: the chain moduli 22 and 26 are replaced by the gears for 11 and 13, and the gears for 71 to 113 add eleven moduli the chain machine never had. With those extra gears the unreported chain-machine stops disappear — the 73 gear rejects both — and every 1928 problem stops exactly once, on its answer (run 1 of the sum of squares, which has no answer in its range, does not stop at all).

14.4.3 The Tiny Sieve (Volume 13)

The Tiny Sieve runs every problem from kbsriram’s drivers directly:

cd code/06/rpi
./run.sh slower.n9999
./run.sh slower.f111
./run.sh slower.sos1
./run.sh slower.sos2
./run.sh slower.m79
./run.sh slower.n93
./run.sh slower.m16

Each driver sets its own rate (50/s or 5,000/s) and card count (19 or 30). To run any of them at the board’s full speed, pass a higher rate to the runner (the faster/ drivers default to 500,000 a second). At the historical rates the board’s run times should match kbsriram’s within a fraction of a per cent; at full speed, all seven problems together take under fifteen seconds.

14.5 Expected Stops

The table gives, for each problem and each set of moduli, the exact number of stops a correct machine makes up to and including the answer (for run 1 of the sum of squares, over the whole range), with the first stops listed. Computed by lehmer_runs.py, which sieves every range in full with Python big-integer bitsets and checks itself against every published answer.

Table 2 — Expected Stops

Problem	Answer at x	19 chains (1928)	30 gears (1932)	8 chains (staged)
9,999,000,099,990,001	400,453	2: 257,749; 400,453	1: 400,453	3,569: 9, 366, 387, 417 …
factor of 3¹¹¹ + 1	145	1: 145	1: 145	1: 145
sum of squares, run 1	none in range	1: 196,113 (false)	0	2,029 over the range
sum of squares, run 2	157,044	2: 102,151; 157,044	1: 157,044	1,101: 147, 195, 423 …
2⁷⁹ − 1	56,523	1: 56,523	1: 56,523	546: 12, 103, 148, 233 …
2⁹³ + 1	6,886	1: 6,886	1: 6,886	20: 106, 516, 741, 832 …
5,283,065,753,709,209	2,694,907 and 5,676,028	117: 6,332, 98,125 …	2: 2,694,907; 5,676,028	176,954

Over their whole ranges the machines stop more often than this — nineteen chains stop 23 times across the full range of 9,999,000,099,990,001, against 22.4 predicted by multiplying the fraction of residues each chain accepts — but a run normally ends at the answer.

Two things in the table are worth noticing. First, the chance prediction — the product of each modulus’s acceptance fraction, times the range — is good: 22.4 predicted against 23 actual for nineteen chains on 9,999,000,099,990,001, 572 against 587 for eight chains on 3¹¹¹ + 1. Lehmer had no computer to sieve a range in advance, and relied on this estimate to know when a machine had enough moduli. Second, the gear machine’s eleven extra moduli matter far more than the chain machine’s speed: they turn 117 stops into 2 on the 1932 demonstration number.

14.6 Expected Run Times

Time to the answer is the answer’s step count divided by the step rate. For the three builds:

Table 3 — Time to the answer is the answer's step count divided by the step rate. For the three builds

Problem	Answer x	Chain, rated 10/s	Chain, Lehmer’s 50/s (original)	Gear, first 500/s	Gear, Lehmer 5,000/s	Tiny Sieve 500,000/s
9,999,000,099,990,001	400,453	11 h 07 min	2 h 13 min	13 min 20 s	1 min 20 s	0.80 s
factor of 3¹¹¹ + 1	145	14.5 s	2.9 s	0.29 s	0.03 s	< 1 ms
sum of squares, run 1 (to its stop)	196,113	5 h 27 min	1 h 05 min	6 min 32 s	39 s	0.39 s
sum of squares, run 2	157,044	4 h 21 min	52 min 20 s	5 min 14 s	31.4 s	0.31 s
2⁷⁹ − 1	56,523	1 h 34 min	18 min 50 s	1 min 53 s	11.3 s	0.11 s
2⁹³ + 1	6,886	11 min 28 s	2 min 17 s	13.8 s	1.38 s	14 ms
5,283,065,753,709,209	5,676,028	6.6 days	31 h 32 min	3 h 09 min	18 min 55 s	11.4 s

Add the time spent at each false stop: none for a machine that checks stops automatically and runs on, and a minute or two each — reading, arithmetic, restarting — for a machine run in faithful mode. The published times line up with the step counts: 400,453 steps at 50 a second is 2 h 13 min against Lehmer’s “about 2 hours”; 145 steps is 2.9 s against “only 4 seconds” (a motor takes time to come up to speed); 6,886 steps at 5,000 a second is 1.4 s against “about 3 seconds”; 56,523 is 11.3 s against “12 s”.

The chain sieve at its rated speed is a patient machine: Lehmer’s own first problem takes an afternoon and an evening. The reproduction’s 12 V gearmotor tops out near 30 steps a second (Volume 11), so the 50/s column is Lehmer’s original, not the reproduction; at the reproduction’s demonstration ceiling the times are about five-thirds of that column. Run it near that ceiling for the short problems and at the rated speed overnight for the long ones.

14.7 Test Protocol

The same protocol serves all three builds.

14.7.1 Before the run

1. Machine checks. Run the build’s own pre-run tests: for the chain sieve, the switch-bus test (Volume 11); for the gear sieve, the all-open and one-gear-blocked tests (Volume 12); for the Tiny Sieve, kbsriram’s selftest (Volume 13). Do not start a recorded run on a machine that has not passed them since it was last disturbed.
2. Load and verify the problem. Generate the loading sheet or plug maps from the scripts, load the machine, and count tabs or plugs back against the sheet. Confirm with the script that the published answer passes every modulus as loaded.
3. Set the start. Every chain on its start link, every gear on its start hole, every card armed at its start phase; counters at zero (or at the start value).
4. Record the problem, date, machine configuration (moduli fitted), step rate, the predicted stop list from the table above, and the room temperature and time.

14.7.2 During the run

5. At each stop, record the counter reading (and the latched count, if the machine has one), the elapsed time, and the result of checking the candidate. For a machine run in faithful mode, compute the candidate from the counter by hand, as Lehmer’s operator did, and check it.
6. Compare every stop with the prediction. A stop at a predicted x is correct, whether it is the answer or a false stop. A stop at any x not in the list means a tab, plug or ring is wrong, or the machine has slipped a step; stop the run and find out which. Reaching a predicted stop without stopping is the more serious failure — the silent one — and also ends the run.
7. On the answer, record it and the time, and verify it independently (multiply the factors; square and add).

14.7.3 After the run

8. Unload the machine and count the tabs or plugs back.
9. Fill in the results sheet.

14.7.4 What counts as success

A run succeeds when the machine stops exactly at the predicted steps up to and including the answer — no more and no fewer — and the answer matches the published one. Run time is recorded but is not a criterion; it depends on how a motor accelerates and how long an operator takes at a false stop.

14.8 Results Sheet

One row per run. Copy the empty rows as needed.

Table 4 — Results Sheet

Problem	Build	Moduli fitted	Rate	Predicted stops (to answer)	Stops observed	Answer	Time	Notes
7663 test	Chain (8)	64 27 25 49 22 26 17 19	10/s	9		79 × 97
factor of 3¹¹¹ + 1	Chain (8)	first 8	50/s	145		25,709,599 × 78,539,161
factor of 3¹¹¹ + 1	Chain (19)	Lehmer’s 19	50/s	145		25,709,599 × 78,539,161
9,999,000,099,990,001	Chain (19)	Lehmer’s 19	10–50/s	257,749; 400,453		1,676,321 × 5,964,848,081
sum of squares, run 1	Chain (19)	Lehmer’s 19	10–50/s	196,113 (false)		none in range
sum of squares, run 2	Chain (19)	Lehmer’s 19, origins at 1/5	10–50/s	102,151; 157,044		785,223² + 1,970,738²
7663 test	Gear	25 and 49 plugged, rest open	50/s	(from chain_tabs.py)		79 × 97
2⁹³ + 1	Gear	all 30	500/s	6,886		529,510,939 × 2,903,110,321
2⁷⁹ − 1	Gear	all 30	500/s	56,523		2,687 × 202,029,703 × 1,113,491,139,767
5,283,065,753,709,209	Gear	all 30	500/s	2,694,907; 5,676,028		59,957 × 88,114,244,437
9,999,000,099,990,001	Tiny	19 cards	50/s	257,749; 400,453		1,676,321 × 5,964,848,081
factor of 3¹¹¹ + 1	Tiny	19 cards	50/s	145		25,709,599 × 78,539,161
sum of squares, run 1	Tiny	19 cards	50/s	196,113 (false)		none in range
sum of squares, run 2	Tiny	19 cards	50/s	102,151; 157,044		785,223² + 1,970,738²
2⁷⁹ − 1	Tiny	30 cards	5,000/s	56,523		2,687 × 202,029,703 × 1,113,491,139,767
2⁹³ + 1	Tiny	30 cards	5,000/s	6,886		529,510,939 × 2,903,110,321
5,283,065,753,709,209	Tiny	30 cards	500,000/s	2,694,907; 5,676,028		59,957 × 88,114,244,437

14.9 Beyond 1932

kbsriram’s board also reruns the six problems that Lehmer, Lehmer and Shanks published in 1970 from the 1965 delay-line sieve DLS-127 (“Integer Sequences Having Prescribed Quadratic Character,” Mathematics of Computation 24, 1970), at the board’s full 500,000 steps a second; his faster/ drivers carry them. They need moduli up to 127 and billions of steps — 8.2 billion for L₁₂₇ — and are beyond either mechanical build: even with a gear for 127 added, the gear sieve at 5,000 a second would need about nineteen days for L₁₂₇ alone. One of them, the pseudosquare L₁₂₇ = 196,265,095,009, produces over 50,000 survivors, because every odd perfect square passes every modulus; DLS-127 printed survivors on paper and could not check them as they arrived, so Lehmer counted survivors instead and binary-searched the range, while the RP2040 simply discards the squares as they come. They are the natural next problems for the Tiny Sieve once the 1928 and 1932 set is done.

The 1928 paper has one more problem that suits the chain sieve exactly: the pseudosquares up to L₆₁. Lehmer ran it by adding one sprung chain at a time — “the chain for 5 was provided with a spring and the machine was set in motion. The first non-square solution obtained was 241. Then the next prime was introduced …” — up to 48,473,881 at p = 61. It is slow (L₆₁ is two million steps), it needs the chains for 53, 59 and 61 that the staged build does not have, and it is the most Lehmer-like way to use the machine: one modulus at a time, watching the answers climb. chain_tabs.py does not carry it as a preset yet; kbsriram’s slower/prob_l61.py has the residue sets.

14.10 What a Reproduction Teaches

Running a published computation on a machine built to the original’s description teaches three things that reading about it does not.

The arithmetic is in the hardware, not in the operator. A loop of 67 links does not compute anything; it simply comes back round every 67 steps. Thirty gears with holes do not compute anything either. The computation is entirely in the choice of which links get a tab and which holes stay open — a few minutes with a table of quadratic residues — and in a coincidence that no single part of the machine knows about. Watching a sieve stop on 145 after a few seconds makes that concrete in a way no description of the Chinese remainder theorem does.

A machine is only as good as its checks. Every build in this series spends more of its design on proving it is right than on running: the chain sieve’s string test, the gear sieve’s alignment rod and blocked-gear test, kbsriram’s roll call, LED walk and fifteen-minute checkpoints. Lehmer’s machines had almost none of this; his check was the answer itself. The two stops his 1928 paper does not report show what that costs: a machine that does what it should, and a record that does not quite say so.

Speed comes from rejection, and rejection comes from moduli. The chain machine and the gear machine differ by a factor of a hundred in speed, but on the 1932 demonstration number the thirty gears stop twice where nineteen chains would stop 117 times. kbsriram’s three-chip breadboard sieve scanned ten times faster than the gear machine and took just as long, because three moduli let one candidate in eight through to the checker. The lesson Lehmer drew in 1934 — that what matters is having “for available moduli all (or nearly all) the small primes” — still holds, and it is the same lesson that, seventy years later, made Bernstein’s direct generation of survivors (Volume 10) the end of the sieving machine.