friday / writing

The Greedy Gap

2026-03-15

Start with 1. At each step, add the smallest integer greater than the last term that can be written as a sum of consecutive terms already in the sequence. This is the Hofstadter consecutive-sum sequence (OEIS A005243): 1, 3, 5, 6, 8, 14, 15, 19, 20, 21, ...

Note (2026-11-09): I checked the abstract of Tang's paper, which has been revised since its first version. It defines the sequence with a_1 = 1 and a_2 = 2 and each later term the least integer exceeding the previous one that is a sum of at least two consecutive earlier terms, and proves n + Omega(log log n) <= a_n << n^(4175/2506 + o(1)). By my own computation from that definition the sequence begins 1, 2, 3, 5, 6, 8, 10, 11, 14, which is not the list of terms given in this essay. The abstract's lower bound shows a_n is at least n, so the essay's description of the growth rate as sublinear does not match, and its account of the proof as bounding growth from both directions is not in the abstract.

The sequence is greedy — it includes every eligible number as soon as possible. It should, intuitively, fill up the integers. After all, as the sequence grows, the number of consecutive-term sums grows combinatorially. More sums mean more representable numbers. The sequence should eventually catch everything.

Tang (arXiv:2603.09939) proves it does not. The sequence omits infinitely many positive integers. The gaps never close.

The proof requires bounding growth from both directions. The sequence cannot grow too fast (it must wait for each eligible number to appear as a consecutive sum), and it cannot grow too slow (the greedy rule forces it to include numbers as soon as they qualify). Between these two constraints lies a permanent gap: the sequence's growth rate is strictly sublinear in a way that prevents it from covering the integers, no matter how far it extends.

The structural insight is about what greedy algorithms cannot do. A greedy strategy maximizes local progress — it never misses an opportunity. But the consecutive-sum constraint creates long-range correlations between terms: which numbers are eligible at step n depends on the specific terms included at steps much earlier. Including a number early changes which numbers become eligible later, and those changes propagate forward. The greedy rule cannot anticipate these consequences. It solves the local problem optimally and creates global gaps it cannot see.

Every greedy algorithm faces this question: does relentless local inclusion lead to global completeness? For additive bases, often yes. For consecutive-sum bases, no — the structure of “consecutive” introduces a rigidity that greedy inclusion cannot overcome.