A rule that counts lets the sum escape

What a missing string of digits leaves behind summed the harmonic series with every term struck out whose denominator contains a given string of digits — 9, or 42, or 314 — and found that it always converges, to a total close to $\ln 10$ times the average time a random stream of digits takes to produce the string. The method was exact and fast, and it depended on one thing: the rule “contains 42” can be checked by a machine with a fixed, finite number of states, reading the digits one at a time and remembering only how much of 42 the number currently ends with. That essay closed by naming the rules it could not handle — the numbers with as many 7s as 3s, the numbers whose digits add up to a prime — rules that no finite machine can follow, because they have to count.

This essay handles them, and the answer is that counting is exactly what lets the series escape. Both of those thinned series diverge. And a whole family of rules sits between them and Kempner’s, in which the series diverges or converges according to a single number: how many independent counts the rule keeps.

The same method, with a counter for a memory #

The block method carries over almost unchanged. All the surviving numbers with $j$ digits form one block, and the block of $j + 1$ digits is built by appending a digit $d$ to each $j$-digit number $n$, giving $10n + d$. Robert Baillie’s trick is to carry, for each block, not only $\sum 1/n$ but $\sum 1/n^2$, $\sum 1/n^3$ and higher powers, and to expand

$$\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}},$$

so that each power sum of the new block is a fixed combination of the power sums of the old one and no term is ever written down.

For a forbidden string the power sums are carried separately for each state of the matching automaton, and the states are few. For “as many 7s as 3s” the state is the balance — the number of 7s minus the number of 3s so far — and it can be any whole number. A 7 raises it by one, a 3 lowers it by one, and any other digit leaves it where it is. A $j$-digit number has a balance between $-j$ and $j$, so the $j$-th block needs $2j + 1$ sets of power sums rather than one or two; and at the end of each block only the numbers whose balance is exactly nought are added to the thinned series. The rule is an automaton with infinitely many states, of which any one block uses only finitely many, and that is all the method needs.

The computation scales the power sums by a power of ten matched to the block, so that nothing underflows over hundreds of blocks, and it sums the first four blocks term by term to start the recursion. The hero shows the result to 120 digits. The full harmonic series gains $\ln 10 \approx 2.3026$ a digit, as a sum that never stops growing explained by grouping. The no-9 series settles at $22.9207$, Kempner’s sum, within about forty digits. The series of numbers with as many 7s as 3s has reached $43.43$ at 120 digits and is still rising; the series of numbers whose digit sum is prime has reached $51.33$, having overtaken it near 65 digits, and is rising faster.

The recursion against ten million terms #

A method that never writes a term down needs checking against one that writes all of them down. Below ten million the check is cheap: run through every number, compute its balance digit by digit, and add $1/n$ to the total for its length when the balance is nought. The figure sets the two side by side. The one-digit block holds $1, 2, 4, 5, 6, 8, 9$, whose reciprocals add to $2.35278$; the two-digit block, with numbers like 10, 11, 37 and 73, adds to $1.59021$; the seven-digit block to $0.83312$. The first four lengths are where the recursion starts, so they agree by construction. From five digits on the recursion computes each block from the one before and nothing else, and the largest disagreement with the direct sums is $3 \times 10^{-14}$, which is rounding in the last places of double precision.

The table also shows the first sign of the divergence. A block of the full series is worth about $\ln 10$, and the survivors’ share of it falls from $2.35$ to $0.83$ over seven digits — slowly, and more slowly as it goes: from the fifth block to the sixth it loses ten per cent, from the sixth to the seventh eight and a half. A Kempner block, by contrast, loses a fixed percentage every time. Forbidding 9 keeps nine tenths of each block, and nine tenths of nine tenths, and the blocks form a geometric series whose sum is finite. Here the ratio of successive blocks creeps towards one, and a series whose ratio tends to one can do either thing. Which it does is decided by how fast.

A block spread over a walk #

The recursion carries every balance, not only the one that is kept, and looking at all of them shows what governs the rate. The figure takes the block of 30-digit numbers, whose reciprocals add to $2.30259$ — $\ln 10$ to four places — and divides that total among the balances. The balance-nought bar, the part the thinned series keeps, is $0.3792$; the bars at $\pm 1$ are a little smaller, and the rest fall away symmetrically.

The shape is a bell, and the reason is that the balance is a random walk. Read the digits of a typical 30-digit number from left to right and the balance takes a step up with chance one in ten, a step down with chance one in ten, and stays put otherwise: a lazy walk, with variance $0.2$ a step. After $j$ steps it is spread like a bell of variance $0.2j$ — the Galton board of the bell curve from coin flips, with most of its pegs missing — and the chance of being back at nought is about $1/\sqrt{2\pi \cdot 0.2j} = 1/\sqrt{0.4\pi j}$. The dashed curve is $\ln 10$ times that bell, with no adjustment, and the bars sit on it. The thinned block is the full block times the chance that a walk of $j$ steps has come home.

That is the difference from Kempner’s series in one sentence. A forbidden string is a finite automaton, and the chance of never having been absorbed by its deadly state decays geometrically, which is the waiting-time argument of two patterns with one chance and different waits in another form — at rate $0.9$ a digit for a single forbidden digit, $0.9899$ for 42. A balance is a walk on an infinite line, and the chance of being at its start decays only like a power of the length, $j^{-1/2}$. Geometric decay makes any series converge. Decay like $j^{-1/2}$ does not.

How fast the blocks shrink #

If the block sums are $\ln 10/\sqrt{0.4\pi j}$, then $\sqrt j$ times the block sum should settle at $\ln 10/\sqrt{0.4\pi} = 2.0541$. The red curve is that product, computed exactly, and it comes down from $2.35$ at one digit to $2.0621$ at 80 digits, approaching the predicted level from above. The approach is slow because the leading digit is not quite like the others — it is never 0, and the reciprocal weights favour small leading digits, which are neither 3 nor 7 — and the effect of one unusual step on a walk of $j$ steps dies away like $1/j$.

So the partial sums of the thinned series, up to numbers of $J$ digits, grow like

$$\sum_{j \le J} \frac{2.0541}{\sqrt j} \approx 4.11\sqrt J,$$

and since a number $N$ has about $\log_{10} N$ digits, the sum over the survivors below $N$ grows like $4.11\sqrt{\log_{10} N}$. It diverges, but at a pace that makes the harmonic series look hasty: to add another ten to the 43.43 of the hero takes the numbers up to about 180 digits, and to reach a hundred takes numbers of about six hundred.

Add a second balance. Keep only the numbers with as many 7s as 3s and as many 1s as 2s, and the state of the counter becomes a point of the square lattice — a walk in two dimensions, stepping in one of four directions with chance one in ten each and resting otherwise. The chance of being home after $j$ steps is now about $1/(0.4\pi j)$, a whole power of $j$, and the blue curve, $j$ times the exactly computed block sum, levels off at $\ln 10/(0.4\pi) = 1.8323$. The partial sums grow like $1.83 \ln J$, the logarithm of the number of digits, which is the logarithm of the logarithm of $N$. That series diverges too, at a rate nobody could observe by adding terms.

Pólya’s theorem in a harmonic series #

The pattern now asks to be pushed. With $d$ independent balances — 7s against 3s, 1s against 2s, 5s against 6s, 4s against 8s — the counter is a lazy walk in $d$ dimensions, and the chance of being home after $j$ steps is about $(0.4\pi j)^{-d/2}$. The series of block sums then behaves like $\sum_j j^{-d/2}$, which diverges when $d/2 \le 1$ and converges when $d/2 > 1$. The figure computes the shares exactly to 4,000 digits, by counting the arrangements in which every pair balances, continues them with the walk’s return chance beyond, and sums $\ln 10$ times the shares to 100,000 digits. One balance has passed 1,296 by then and is climbing like a square root; two have reached 21.98 and are climbing like a logarithm; three have settled at about 3.51 and four at about 1.26, and over the last factor of ten in length the three-balance sum moves by less than a twentieth.

This is Pólya’s recurrence theorem, met in an unexpected place. George Pólya proved in 1921 that a random walk on the integer lattice returns to its starting point with certainty in one and two dimensions and with probability less than one in three or more, and a walk that comes home drew the reason: the expected number of returns is the sum of the return chances, $\sum_j j^{-d/2}$, which is infinite exactly when $d \le 2$. The harmonic series thinned by $d$ balances is that same sum with every term multiplied by $\ln 10$. Whether the series converges is whether the walk is recurrent, and the numbers with as many 7s as 3s, as many 1s as 2s and as many 5s as 6s form a convergent series for the same reason that a drunkard in space may never find the way home.

The figure’s sums are not quite the thinned series. They take each block to be $\ln 10$ times the share of survivors, which ignores the leading-digit effect the exact computation sees; that changes each term by a factor tending to one, and so it can change the totals but not the question of convergence. The exact block sums for one and two balances, in the previous figure, confirm that the factor does tend to one.

Digits that add up to a prime #

The second rule the earlier essay named counts too, with a different counter. The state is the digit sum so far, and a $j$-digit number has a digit sum between 1 and $9j$; the recursion carries a set of power sums for each, about 1,350 of them at 150 digits, and keeps the numbers whose final digit sum is a prime.

The digit sum of a typical $j$-digit number is about $4.5j$, spread over a window a few times $\sqrt{8.25j}$ wide, and near $4.5j$ the primes have density about $1/\ln(4.5j)$, as counting what has no formula found for the primes everywhere. So the block sums should be about $\ln 10/\ln(4.5j)$, and the figure divides the exact block sums by that prediction. The ratio stays close to one, averaging $1.067$ over the last twenty blocks, and it wobbles: the window of likely digit sums is only a few dozen wide, and over a window that narrow the primes are visibly uneven — between 600 and 660, for instance, there are eleven primes where the density predicts nine. The wobble is the primes’ own irregularity, seen through a harmonic series.

So these blocks shrink like one over the logarithm of the length, far more slowly than any power, and the partial sums grow like the number of digits divided by its logarithm. This series diverges almost as fast as the harmonic series itself — about a sixth of the full series’ gain per digit at 120 digits, a share falling only logarithmically — which is why it overtakes the balanced series in the hero and leaves it behind. The two rules sit at different places on one scale. A finite automaton makes the share decay geometrically; a walk in $d$ dimensions makes it decay like $j^{-d/2}$; a test of primality on a sum makes it decay like $1/\ln j$; and the series converges only for the first and for $d \ge 3$.

What the computation settles and what it leaves #

The block sums are exact up to rounding, by a recursion checked against ten million directly added terms, and they extend to 120 digits for the hero, 80 for the rates and 150 for the digit sums; nothing beyond those lengths is computed term by term or by recursion. The divergence of the balanced series is not read off the curves, which no finite computation could show; it follows from the local limit theorem, which says the walk’s return chance is $1/\sqrt{0.4\pi j}$ to within a factor tending to one, together with the comparison $\sum j^{-1/2} = \infty$. The convergence for three balances follows the same way from $\sum j^{-3/2} < \infty$. The figures show the constants arriving where the theorem puts them, which is evidence the computation is right, not proof that the series behaves.

The values of the convergent series are not computed exactly. The three-balance and four-balance totals in the figure are $\ln 10$ times shares, so they estimate the true sums without leading-digit corrections, and no figure here gives the sum of $1/n$ over the numbers with three balanced pairs to more than about one significant figure. Doing so needs the recursion carried over a three-dimensional array of balances, which grows like the cube of the length and becomes expensive within a few dozen digits.

And the digit-sum series’ divergence rests on the prime number theorem applied to numbers near $4.5j$, with the window of digit sums growing like $\sqrt j$. That the ratio in the last figure tends to one, rather than merely staying near it, needs the primes to be evenly spread over windows of width $\sqrt j$ around $4.5j$ — which is true, but is a theorem about primes in short intervals, of the kind the longest wait for a prime showed can be delicate.

Still open: rules with no counter at all #

Every rule here is decided by a counter, finite or infinite, read along the digits from left to right, and for every such rule the series’ fate is decided by how fast the counter’s chance of ending in an accepted state decays. That covers a great deal, but not everything. Keep only the numbers whose digits, read as a number in base three, are prime; or the numbers $n$ for which the $n$-th digit of $\pi$ is a 7; or the numbers that are not the sum of two squares. The first two have no counter of this kind at all, and the third has one only after factoring. For rules like these the share of survivors among $j$-digit numbers need not decay in any regular way, and whether the thinned harmonic series converges has to be settled by whatever is known about the rule, one case at a time.

There is also a finer question about the rules that do have counters. A coin in front of every term found a harmonic series whose fate was decided by the squares of its terms; here the fate is decided by a walk, and both say that thinning or signing the terms changes the answer only through how fast a probability decays. Kempner’s series converge to totals that the earlier essay matched to the waiting time for a string, $\ln 10$ times the wait plus a leading-digit correction. The three-balance series converges too, and its total is presumably $\ln 10$ times something like the expected number of returns of a lazy walk in three dimensions, plus a correction — Watson’s integrals give that expected number exactly for the simple walk — but the correction depends on the leading digit in a way no formula here captures. A closed expression for the sum of $1/n$ over the numbers with three balanced pairs is not known, and it is not obvious that one exists.

Counting is what lets the sum run #

Thin the harmonic series by a rule that a finite automaton can check and the blocks shrink geometrically, so the series converges; thin it by a rule that has to count, and the blocks shrink only as fast as the counter’s chance of ending in the right place. For as many 7s as 3s that chance is a lazy walk’s return probability, $1/\sqrt{0.4\pi j}$, the blocks times $\sqrt j$ settle at $2.0541$, and the series diverges like $\sqrt{\log N}$. With $d$ balances the walk is $d$-dimensional and the series diverges for $d$ of one or two and converges for three — Pólya’s recurrence theorem, line for line. And when the digits must add up to a prime the blocks shrink like one over a logarithm, and the series runs on nearly as fast as the one it was cut from.