The Greedy Gap

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, …

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.