Growing is not climbing

A repetition is a guess read every octal code of up to three digits the way a period search reads it, one heap at a time, and scored each reading against the period Guy and Smith’s window eventually certifies. It set aside 220 codes whose period could not be certified within 2,400 heaps, and it counted 178 of them as growing: their largest value over heaps 1,600 to 2,400 was larger than over 800 to 1,600, so no pure period could ever describe them. It closed on a guess about those 178. Many of them, it said, are probably arithmetically periodic — their values repeat with period p plus a fixed increase c each time round, $G(n + p) = G(n) + c$ — and a reader looking for that pattern would be fooled the way the pure readings were fooled, perhaps for longer.

That guess can be tested in an afternoon, and it is wrong. Give the reader a constant to add and point it at the 220 codes, and it reports a climb at almost every depth — 246,048 readings in the first 1,200 heaps — and every one of them breaks within six periods. The same reader pointed at the hexadecimal codes where a climb is real finds it every time, after false readings that last no longer than the octal ones do. The octal codes that grow are not climbs waiting to be read. They are growing in some other way, and the way can be measured even though it cannot yet be named.

A reader given a constant to add #

The reader is the earlier essay’s reader with one clause changed. At depth d, with the values of heaps 1 to d − 1 in hand, it takes the earliest heap s and then the shortest period p such that the difference $G(n + p) - G(n)$ is one constant $c$ for every n from s up to the last value read, the constant is not nought, and the pattern covers at least two full periods. Requiring c ≠ 0 keeps the pure periods out, since those were the earlier essay’s subject, and leaves exactly the pattern the guess was about. Heap 0 is excluded for the reason given there: the argument that certifies a pattern shifts one part of a split down by a period, and a split never leaves an empty heap.

The two lanes of the picture above are the whole result in miniature. The hexadecimal code ·28 is one a period with a constant added found climbing: its values repeat with period 53 and rise by 16 each time round. The reader is wrong about it seventy-one times, nearly all of them for a heap or two, and from depth 107 it is right and stays right. The octal code ·6 — take one counter and leave one heap or two, one of the codes the subject has been waiting on for decades — is read over a thousand times in the same span and is never right, because there is nothing to be right about. Each box in its lane is a climb that the next few values refute.

Where the climb is real #

The reader can only be trusted on the octal codes if it can be trusted where the answer is known, so it was run first on the 71 two-digit hexadecimal codes that the essay on the hexadecimal climb by three found climbing. Hexadecimal codes add a fourth bit to each digit — a move may leave three heaps — and the third digit found that among them a climb is the ordinary way to settle rather than the exception.

On every one of the 71, the reading the reader settles on is the period, start and climb that the earlier sweep found by a different search, so the two methods agree code by code. The right reading arrives early: at the median by depth 5, because thirty-odd of these codes climb by one with a period of one or two from the very first heap, and at worst by depth 107, on ·28 and ·29, whose period of 53 needs two full repetitions to be seen at all. Thirteen codes are never read wrongly. The others are read wrongly 377 times between them, and those false readings are short: 307 of them hold for only the two periods the reader demands, and the longest holds for seven, on ·8b and ·8f: a climb of one every two heaps from heap 1 that heap 15 breaks.

That last number is the one to keep in mind. A false climb on a code that really climbs lasts at most seven periods. Nothing about a hexadecimal false reading announces itself as false; it is broken by the next value, the way a pure false reading was, and the right reading comes after it.

Two hundred and forty-six thousand readings, all false #

On the octal side every reading is false by construction: a code whose climb held to the end would have shown up as a long reading still standing at the last depth read, and the only readings standing there are 206 that had held for two periods and no more. What can be measured is how long each held.

They held for no time at all. Of the 246,048, 240,687 held for fewer than three periods, 4,714 reached three, 419 four, 88 five and 140 six, and not one reached seven. Ninety-five per cent of them have a period of one, which is to say that three neighbouring values happen to be in arithmetic progression — 4, 5, 6 or 9, 7, 5 — and a reader whose rule says two periods is a pattern takes three values as a climb. Only 9,929 have period two and 1,031 period three; past that the counts are in hundreds and tens, and the longest period read at all is nine. The guess pictured a climb with a long period, held convincingly over many heaps before something broke it. There is no such thing among these codes. The longest reading with a period of two or more holds four and a half periods, and it is the same reading on eight codes, ·064 to ·067 and ·404 to ·407: values climbing by one every two heaps across the first ten heaps, before any heap is large enough for a split to interfere.

The surprising part is the comparison. The false climbs on the octal codes are not longer than the false climbs on the hexadecimal codes; the longest is shorter, six periods against seven. And they are not longer than the false pure readings the earlier essay counted on the codes that settle, where a reader demanding six repetitions believed none of 4,684. Three different readers on three different families — pure periods on settled octal codes, climbs on hexadecimal codes, climbs on unsettled octal codes — and in every one a false reading dies within about six periods. That ceiling is a property of how a short pattern is found in values that are locally irregular, not of the family, and it means the length of a reading never distinguished the octal codes from the hexadecimal ones. The only thing that does is whether, after the false readings, a right one arrives. On the octal codes it does not.

What ·6 actually offers #

It is worth seeing what a false climb looks like on a code nobody has settled, because “three values in progression” undersells how plausible some of them are.

From heap 4 the values of ·6 run 0, 1, 2, 3 — a climb of one per heap, the longest reading ·6 ever offers, four periods long — and heap 8 is worth 1. From heap 28 they run 1, 2, 0, 1 and then 2, 3, 1, 2 and then 3, 4, 2, 3: a block of four values with one added each time round, three times, a pattern any reader would take seriously. Heap 41 is worth 2 where the pattern says 5. That reading is the closest ·6 comes, in 1,200 heaps, to the shape of a hexadecimal climb, and it is gone in thirteen heaps. Across the whole range ·6 is read 1,128 ways, 92 of them with a period longer than one, and none holds five periods.

The same reader on ·28 has the same experience for a hundred heaps — a flicker of short readings, each broken by the next value or the one after — and then a pattern arrives that the values never break. That is what the guess expected of the octal growers, and it is the thing that never happens.

A climb is a growth rate #

Nothing about the readings proves that no octal code climbs. A climb that started at heap 50,000 would be invisible to a reader stopped at 1,200, and the honest position on these codes is the one the sequence nobody has settled states for ·007: they settle somewhere beyond reach, or nowhere. But a climb has a consequence that can be checked without reading anything. If $G(n + p) = G(n) + c$ from some heap on, then the largest value up to heap n grows in proportion to n, at rate c/p per heap, for ever. A sequence that climbs has a maximum that is eventually a straight line on a plot of value against heap, and on a plot with both axes logarithmic it is a line of slope one.

The growing codes do not grow like that. Their running maxima rise in steps, as a mex sequence’s must — a new largest value appears only when some heap’s options happen to cover everything below it — and the steps come further apart. ·564, the fastest-growing code of the 178, has a largest value of 134 at heap 600, 432 at heap 2,400 and 1,155 at 9,600: growth by a factor of 3.2 and then 2.7 over two fourfold stretches, where proportional growth would multiply by four each time. ·6 goes 21, 72, 248 — a factor of about 3.4 twice, steady and below four. ·007, the famous one, goes 35, 97, 260.

The exponent is the cleanest way to say this. Over a stretch from heap a to heap b, the exponent is $\log(M_b / M_a) / \log(b / a)$, where $M_n$ is the largest value up to heap $n$: one for growth in proportion to the heap, a half for growth like a square root, nought for a maximum that has stopped. A climb, however long its period and however small its constant, drives the exponent to one.

No growing code is near one. Over the later stretch the largest exponent is 0.895, on ·126, and 71 of the 178 are below a half. The direction is mostly downward: 138 codes grow more slowly from 2,400 to 9,600 than from 600 to 2,400, and the 40 that speed up do so by a few hundredths. Nothing here is a proof, since a code could grow at 0.8 for ten thousand heaps and then begin a climb, and the plot cannot rule that out any more than the readings can. What it does rule out is the picture behind the guess, of codes already climbing whose climb had not yet been recognised. A climb that had begun anywhere inside the computed range would show as an exponent near one in the later stretch, and none does.

There is a reason to expect sub-proportional growth that has nothing to do with these particular codes. A heap’s value is the least number missing from its options, and an octal option is a pair of smaller heaps combined by exclusive-or. For a new largest value to appear at heap n, every smaller number has to be hit by some split — and the splits of n are about n/2 pairs of values from a range whose own size is the maximum so far. A climb would demand a new record value every p/c heaps for ever, each one needing the splits to cover everything beneath a larger and larger number. The growing octal codes behave as if that covering gets harder: records arrive, but further apart. The hexadecimal codes can climb, and the hexadecimal climb by three traced the difference to the one move they have and octal codes lack: leaving three heaps offers options worth a three-fold exclusive-or, which reach values a two-fold one from the same heap cannot, so the mex has more to climb over. Among its two-digit codes not one octal code climbed. The readings here carry that from two digits to three, and from a search for a settled climb to a reader that would have reported any climb at all.

Growing, for a while #

Following the maxima to 9,600 heaps turned up something about the word growing itself. The census that sorted the 220 codes asked one question — whether the largest value over heaps 1,600 to 2,400 beat the largest over 800 to 1,600 — and it was the right question to ask of 2,400 heaps. It is not a good question to ask of 9,600.

Eight of the 178 had the same largest value at heap 9,600 as at heap 2,400. Four of them — ·245, ·247, ·255 and ·257, which share one sequence — reached 129 at heap 1,689, inside the census’s later stretch, and that one new record is the whole reason they were counted as growing. Followed to 20,000 heaps they have not produced a value above 129, and they have not produced a period either. They are, on present evidence, bounded and unsettled: the same class as the 42 the census called bounded, and the class every famous open problem among octal games belongs to. The other four — ·56 and its three neighbours — sat at 59 from heap 1,795 for more than eight thousand heaps and then jumped to 61 at heap 9,892. A census at 9,600 would have called them bounded, and it would have been wrong in the other direction.

So the count of 178 growing codes is a count of codes whose maximum rose in one window, and the line between growing and bounded among unsettled octal codes is only as sharp as the window that draws it. That matters for the question this essay was asked, since the guess was about the 178 and four of them are not growing in any useful sense. It matters more for what it says about the 42: a bounded unsettled code is one whose last record has not been followed by another yet, and ·56 shows the wait can be eight thousand heaps.

What the reader assumes, and what the picture cannot show #

The convention. A reading here is the earliest start and then the shortest period with a constant non-zero difference across at least two full periods of the values read so far; it holds at depth d exactly when the pattern survives every value below d. “Held for k periods” means (last depth held − start) ÷ period. The octal codes are every code of one to three digits whose period was not certified within 2,400 heaps; their values were computed to 2,400 and read to 1,200. The hexadecimal codes are the 71 two-digit codes whose climb the earlier sweep found within 600 heaps, read to 600. Growth exponents use the running maximum at 600, 2,400 and 9,600 heaps, computed by the mex rule with the full split, and the stalled codes were followed to 20,000.

No window certifies a climb here. The hexadecimal climbs are what a search finds and holds to the end of its range, and the earlier essays on them say so; this essay uses them only as a family where the reader has something right to find, and that the reader agrees with an independent search on all 71 is a check on the reader, not a proof about the codes. There is a window theorem for arithmetic periods, and nothing here depends on its exact form, because no octal reading came near enough to any window to need one — the gap a strategy is not a certificate draws between holding an answer and being able to show it never opens, because no answer is ever held.

What the picture cannot show is whether any of these codes climbs beyond 9,600 heaps. The readings show that none climbs inside the range read; the exponents show that none is growing at a rate a climb would force inside the range computed. A climb that begins later is excluded by neither. It would be a strange thing — a sequence that spends ten thousand heaps growing ever more slowly and then commits to growing in proportion for ever — but octal games have been strange before, and the subject has a long list of sequences that looked settled for a very long time and were not.

Still open: what kind of growth this is #

The growing octal codes are neither periodic nor climbing on the evidence here, which leaves the question of what they are doing. Their maxima grow with exponents that mostly fall from one fourfold stretch to the next, which is the signature of growth slower than any power — a logarithm, or a square root of a logarithm, or records whose spacing itself grows — but three points on a curve do not say which. The values that keep arriving counted the distinct values of ·007 and found the count still rising at six thousand heaps; the maximum is a coarser thing than the count and easier to follow far. The measurement is the running maximum of ·6 and ·564 to a million heaps, where the odd values keep coming showed a typed-array mex reaches a hundred thousand in seconds: if the record values arrive at heaps spaced in a fixed ratio, the growth is logarithmic and the octal codes that grow have a law of their own; if the spacing keeps changing, they do not even have that.