What a missing string of digits leaves behind

A sum that never stops growing ended its account of the harmonic series with a deletion that changes everything. Strike out every term $1/n$ whose denominator contains the digit 9, and what is left converges, because the numbers without a 9 thin out geometrically while the terms shrink only like $1/n$. That essay summed the survivors in blocks of equal length, saw each block contribute nine tenths of the one before, and extrapolated to a total of about 22.9207, noting that the terms below a hundred million reach only 58 per cent of it.

That leaves two questions this essay takes up. The first is how to compute the total exactly, to the limit of ordinary arithmetic, when no amount of term-by-term addition comes close. The second is what the total depends on. Leaving out a different digit gives a different sum, and leaving out a string of digits — every number containing 42, say — gives another. Computed for every digit, every pair of digits and a sample of longer strings, the sums turn out to be governed by a quantity from a different subject entirely: the average time a random sequence of digits takes to produce the string, the quantity that decides which of two patterns of coin tosses tends to come first.

Summing a block without adding its terms #

The block method is the right start because the series is naturally organised by length. All the admissible numbers with $j$ digits make one block, and each block is built from the one before: every admissible $(j+1)$-digit number is an admissible $j$-digit number $n$ with a digit $d$ appended, which is to say $10n + d$. The trick, due to Robert Baillie in 1979, is to carry not one sum per block but many: the sum of $1/n$, of $1/n^2$, of $1/n^3$, and so on. Expanding the new reciprocals in powers of $d/(10n)$,

$$\frac{1}{(10n + d)^k} = \sum_{w \ge 0} \binom{k + w - 1}{w} \frac{(-d)^w}{10^{k + w}}\, \frac{1}{n^{k + w}},$$

expresses each power sum of the new block as a fixed combination of the power sums of the old one. No term of the new block is ever written down. A block of a billion billion numbers is summed by a few hundred multiplications.

The expansion converges fast because $d/(10n)$ is small. The blocks of up to four digits are summed directly, term by term, so that wherever the expansion is used $n$ is at least ten thousand and each extra power gains about five decimal places.

Ignoring the appended digit altogether — treating every five-digit and longer number as ten times its prefix — gets the no-9 total wrong by $2.7 \times 10^{-3}$. One correction term brings the error to $8 \times 10^{-7}$, two to $3.5 \times 10^{-10}$, three to $1.9 \times 10^{-13}$, and a fourth leaves nothing the arithmetic can see. The computation then runs block by block until the blocks are negligible, four hundred of them for a single forbidden digit, and gives $22.920676619264$, matching the $22.92067661926415$ that Baillie published to the digits it shares. Two independent checks stand behind every figure here: the block sums for the first seven lengths agree with adding the terms below ten million one at a time to ten decimal places, for the digit 1 and for the digit 9, and the published value is reproduced.

Ten digits, ten sums #

Every digit can be forbidden, and the next figure does all ten.

The sums run from $16.177$, with every 1 forbidden, to $23.103$, with every 0 forbidden, and between them in order: $19.257$ for 2, $20.570$ for 3, $21.327$ for 4, $21.835$ for 5, $22.206$ for 6, $22.493$ for 7, $22.726$ for 8 and $22.921$ for 9. The order is not an accident of arithmetic. In each block the largest terms are those with the smallest leading digit, and forbidding 1 removes every number beginning with 1 — the one-digit 1, the two-digit 10 to 19, the three-digit 100 to 199 — which are the largest terms of their blocks. Forbidding 9 removes the leaders 9, 90 to 99, 900 to 999, which are the smallest. Forbidding 0 removes no leading digit at all, since no number begins with 0, and so loses the least.

All ten sums sit near one value, the dashed line at $10 \ln 10 \approx 23.03$, with 0 a little above it and the rest below, and that value is the first sign of a pattern. It is the sum for any digit with the leading-digit effect removed, and where it comes from is clearest when the forbidden object is longer than one digit.

A string instead of a digit #

Forbid the string 42, so that 42, 142, 420 and 9,042 are all struck out but 4,312 survives. The surviving numbers thin out more slowly than before, since a random block of $j$ digits is far likelier to avoid a particular pair than a particular single digit, and the sum is larger: $228.45$, ten times what forbidding a single digit leaves. The hero figure does the same for all hundred pairs from 00 to 99, and the hundred sums fall into two groups.

The ninety pairs of two different digits leave sums between $220.89$ and $230.40$, close to $100 \ln 10 = 230.26$. The ten repeated pairs, 00 to 99, leave sums between $244.78$ and $253.29$, close to $110 \ln 10 = 253.28$. Within each group the spread follows the leading digit, as it did for single digits. Between the groups there is a gap of about ten per cent, and nothing about which numbers are struck out explains it at a glance. Forbidding 42 and forbidding 99 remove the same proportion of the two-digit numbers, one in a hundred, and nearly the same proportion of longer ones. Yet the sum without 99 is larger by a tenth.

The rate a string allows #

The block method still works for a string, with one change: the blocks must remember how much of the forbidden string their numbers currently end with. For 42, a number ending in 4 is one digit away from disaster, and a number ending in anything else is not. That memory is a small finite automaton, the same machine that searches a text for a word, and the block sums are carried separately for each of its states. A string of $k$ digits needs at most $k$ states, and the recursion is otherwise unchanged.

The automaton does more than organise the computation. Its digit-count matrix — for each pair of states, how many of the ten digits move one to the other — has a largest eigenvalue $\lambda$, and the number of admissible $j$-digit numbers grows like $\lambda^j$ against the $10^j$ of all numbers. So the proportion that survives at length $j$ falls like $\rho^j$ with $\rho = \lambda/10$, and the block sums, which are that proportion times roughly $\ln 10$, fall at the same rate.

The lines are straight, and their slopes are exactly the eigenvalues: $\rho = 0.9$ for any single digit, $0.98989795$ for 42, the larger root of $x^2 - 10x + 1$ divided by ten; $0.99083269$ for 99, from $x^2 - 9x - 9$; $0.99899799$ for 314; $0.99909756$ for 999. The measured ratio of successive blocks agrees with the eigenvalue to a millionth for each of the five, and the agreement is exact in the limit.

The two automata for 42 and 99 differ in one entry, and the difference is the whole story. Each has a safe state and a risky one — ending in 4, or ending in 9 — and one deadly digit from the risky state. For 42, a 4 typed in the risky state keeps the number risky, so a run of 4s stays exposed to a 2 for as long as it lasts. For 99, the digit that would keep the number risky is the deadly one itself, so every surviving step from the risky state returns to safety. Put the other way, occurrences of 99 come in clumps — 999 contains it twice and 9999 three times — so a given number of occurrences is spent on fewer numbers, and more numbers escape it altogether. The slightly slower decay is worth ten per cent of the total because the total is a geometric series in $\rho$, and a geometric series with ratio near one is acutely sensitive to it: the sum of the blocks behaves like $1/(1 - \rho)$, which is about 99 for 42 and 109 for 99.

Why each block is worth ln 10 #

The prediction below needs one more ingredient, and it is the reason a logarithm appears at all. Add up $1/n$ over every number with exactly $j$ digits, from $10^{j-1}$ to $10^j - 1$, with nothing struck out. For one digit the sum is $2.829$; for two, $2.348$; for three, $2.307$; and from there it settles onto $\ln 10 = 2.302585\ldots$, because the sum of $1/n$ from $a$ to $b$ is the area under $1/x$ between them to within a correction of order $1/a$, and the area from $10^{j-1}$ to $10^j$ is $\ln 10$ whatever $j$ is. Each order of magnitude of the harmonic series is worth the same amount. That is the divergence of the full series seen block by block — infinitely many blocks, each worth $\ln 10$ — and it is the same observation as Oresme’s grouping, which a sum that never stops growing used with powers of two in place of powers of ten.

A forbidden string turns this constant sequence into a geometric one. The proportion of $j$-digit numbers that survive falls like $\rho^j$, and if the survivors were spread evenly through the block, the block’s sum would be about $\rho^j \ln 10$. They are not quite spread evenly — the struck-out numbers include whole runs of leading digits — and that unevenness is the correction examined below. But to first order the total is $\ln 10$ times the sum of $\rho^j$, which is $\ln 10/(1 - \rho)$, and everything now depends on how close $\rho$ is to one.

The matching automaton is also a Markov chain in disguise. Feeding it uniformly random digits moves it between its states with fixed probabilities, and $\rho$ is the rate at which the chance of never having reached the deadly state decays. That is the reading that connects the sum to waiting.

Waiting for a string to appear #

The quantity $1/(1 - \rho)$ has a second meaning that makes the pattern memorable. Feed random digits one at a time and wait for a given string to appear. For a string of $k$ digits that does not overlap itself — whose beginning is never also its end — the average wait is $10^k$. For a string that does overlap itself the wait is longer, and John Conway gave the rule, in the form a coin that lets the first player win used for Penney’s game: add $10^m$ for every $m$ from 1 to $k$ at which the first $m$ digits of the string equal its last $m$. So 42 has wait $100$, 99 has wait $100 + 10 = 110$, 999 has $1{,}110$, 909 has $1{,}010$ and 2525 has $10{,}100$. A self-overlapping string takes longer to appear, on average, because its near misses are partly on the way to the next attempt.

For long strings the dominant eigenvalue satisfies $1 - \rho \approx 1/\text{wait}$, so the sum of the blocks is about the wait times the sum over one block of all numbers, and the sum of $1/n$ over all $j$-digit numbers is close to $\ln 10$ for every $j$. That gives a prediction in one line: the sum of $1/n$ over the numbers avoiding a string is about $\ln 10$ times the average time to wait for it.

The prediction holds better the longer the string. Among single digits the largest gap between the sum and ln 10 times the wait is thirty per cent, for the digit 1. Among pairs it is $4.1$ per cent, among the three-digit strings drawn here $0.18$ per cent, and among the four-digit strings $0.016$ per cent. The string 999 leaves $2{,}555.8685$ against $1{,}110 \ln 10 = 2{,}555.8695$; the string 9999 leaves $25{,}581.7203$ against $11{,}110 \ln 10 = 25{,}581.7204$, agreement to eight figures. So the ten per cent between 42 and 99 is the ten per cent between waiting 100 digits and waiting 110 — the overlap that two patterns, one chance, different waits found for coin tosses — and the harmonic series reads a string’s overlaps with itself as faithfully as Penney’s game does.

What is left over #

Once the wait is divided out, what remains is the leading-digit effect that ordered the single digits, and it can be seen cleanly on the pairs.

Grouped by first digit, the ratio climbs steadily: about $0.971$ for strings beginning with 1, $0.984$ with 2, and so on to $0.9996$ with 9, while strings beginning with 0 sit at $1.0003$. A string that begins with 1 is struck out wherever it appears, including at the front of numbers, where it removes $1x$, $1x0$ to $1x9$ and every longer number that starts with it — the largest terms of their blocks, by the same reasoning as before. A string that begins with 9 removes leaders too, but the smallest ones. A string that begins with 0 can never stand at the front of a number, so it never removes a leader, and the sum it leaves is a shade more than the wait predicts. The effect fades as strings lengthen because a longer string begins fewer numbers: for a string of $k$ digits, the numbers it begins are a share of about $10^{-k}$ of each block, so the correction falls like the share of numbers the string can lead. Benford’s law is the same asymmetry in another setting — the leading digit 1 carrying far more than a tenth of the weight — and here it is the whole of the deviation from the waiting-time formula.

What the computation cannot say #

The figures settle numbers, not theorems. Each sum is computed to about fourteen significant figures, and its correctness rests on the recursion, the direct summation it was checked against below ten million and Baillie’s published value for the digit 9. The relation to the waiting time is a different kind of statement. The argument for it keeps only the dominant eigenvalue and treats the sum over a block of $j$-digit numbers as exactly $\ln 10$, and both approximations improve as strings lengthen; the figures show the gap shrinking from thirty per cent to under two hundredths of one per cent over strings of one to four digits. They do not show a bound on the gap for every string, and an argument with an explicit error term would have to control the eigenvalue’s distance from $1 - 1/\text{wait}$ and the leading-digit correction together.

Nor does anything here say what happens to the struck-out numbers’ own sum, which is infinite in every case: the numbers that do contain 42 still make the harmonic series diverge. The essay measures what is left, and the remainder is finite precisely because the forbidden string, given long enough, appears in almost every number.

Still open: the slow series that look fast #

The Kempner series are a family of convergent series whose partial sums are useless: to get the no-9 total to six figures by adding terms, the terms up to beyond $10^{120}$ would be needed, and for a three-digit string the figure is past $10^{14{,}000}$. The block method sidesteps that entirely, but it depends on the forbidden pattern being describable digit by digit, by a finite automaton. For series that delete terms by a rule no automaton can follow — the numbers whose digits sum to a prime, the numbers with as many 7s as 3s — there is no comparable method, and whether such series converge, let alone to what, is decided case by case or not at all.

The series two sign patterns that land together studied, with each term given a random or patterned sign rather than deleted, raised the same issue from the opposite side: a series whose behaviour is fixed by arithmetic far out in its tail, where no partial sum reaches. Here the arithmetic has a clean answer — an eigenvalue, a waiting time and a logarithm — because deleting a string is a regular rule. What sums are computable when the rule is irregular is a question the block method cannot touch.

Ten per cent for an overlap #

The harmonic series with its nines deleted converges to $22.92$, and the number is unremarkable until it is compared. Deleting a 1 instead leaves $16.18$, deleting 42 leaves $228.45$ and deleting 99 leaves $253.28$, and each of those differences has a reason that can be stated without computing anything: leading digits for the first, and for the last two the average wait for the string in random digits, which is longer by a tenth for a string that overlaps itself. The sum of $1/n$ over all the numbers of one length is $\ln 10$, the geometric series of surviving blocks multiplies it by the wait, and the result is a slowly convergent series whose total, to four figures, can be predicted from the string alone.

That the harmonic series should know Conway’s rule for Penney’s game is the connection worth keeping. Both are measuring the same thing: how long a pattern can avoid turning up in a random stream of digits, whether the stream is a coin being tossed or the decimal digits of the integers counted in order.