The Hofstadter consecutive-sum sequence omits infinitely many positive integers

This paper resolves a conjecture from OEIS entry A005243 by proving that the greedy self-generating sequence defined by Hofstadter, where each term is the smallest integer greater than the previous one representable as a sum of at least two consecutive earlier terms, omits infinitely many positive integers.

The Gist

Imagine you are building a tower of blocks, but with a very specific, greedy rule: You can only add a new block if its height is the sum of two or more blocks that are already sitting right next to each other in your tower.

You start with two blocks: one of height 1 and one of height 2.

• Can you make 3? Yes, $1+2=3$. So you add a block of height 3.
• Can you make 4? You look at your tower (1, 2, 3). The sums of neighbors are $1+2=3$and$2+3=5$. You can't make 4. So, 4 is skipped.
• Can you make 5? Yes, $2+3=5$. Add it.
• Can you make 6? Yes, $1+2+3$(wait, the rule says "consecutive," so$1+2=3$and$2+3=5$and$3+5=8$... actually, looking at the sequence in the paper: 1, 2, 3, 5, 6... Ah,$3+5$ is not consecutive in the list yet? No, the rule is: take the current list, find the smallest number larger than the last one that can be formed by adding a chunk of neighbors.
  • Current list: 1, 2, 3, 5.
  • Last number: 5.
  • Next candidate: 6. Can we make 6 from neighbors? $1+2+3=6$. Yes! Add 6.
  • Next candidate: 7. Neighbors sums: $2+3=5$,$3+5=8$,$5+6=11$... No 7. 7 is skipped.

This is the Hofstadter Consecutive-Sum Sequence. It's a game of "fill in the gaps" where you are forced to skip numbers if they can't be built from your current neighbors.

The Big Question

For decades, mathematicians (including the famous Douglas Hofstadter) wondered: Does this sequence eventually fill in every single missing number? Or, does it keep skipping numbers forever?

It looked like it was filling in most numbers. The list starts:
1, 2, 3, 5, 6, 8, 10, 11, 14...
It skips 4, 7, 9, 12, 13...
But maybe it just takes a long time to catch up? Maybe by the time you reach a billion, there are no more skips?

The Discovery: The "Infinite Gap"

In this paper, the author, Quanyu Tang, proves that no, the sequence never catches up.

He shows that the sequence omits infinitely many positive integers. No matter how far you go, there will always be new numbers that the sequence simply cannot build.

The Analogy of the "Excess":
Imagine the sequence is a runner trying to keep pace with a finish line that moves forward by 1 unit every second.

• If the runner is perfect, they are at position $n$ at time $n$.
• Tang proves that this runner is actually getting faster than the finish line.
• The gap between where the runner is ($a_n$) and where they "should" be if they filled every number ($n$) keeps growing forever.
• Because the runner is sprinting ahead, they are leaving a trail of empty spots (the skipped numbers) behind them that never gets filled.

How Did He Prove It? (The Detective Work)

Tang used a clever two-step logic puzzle:

1. The "Linear Tail" Trap: He assumed the opposite: that the sequence does eventually fill all gaps. If that were true, the sequence would eventually settle into a boring, predictable pattern (like $100, 101, 102, 103...$).
2. The "Power of Two" Bomb: He then looked at the special numbers that are powers of 2 (like 2, 4, 8, 16, 32...). There is a mathematical rule that says powers of 2 cannot be made by adding consecutive numbers.
3. The Contradiction: If the sequence were boring and predictable (linear), it would eventually have to try to "build" a power of 2 using its neighbors. But because of the rules of math, it's impossible to build a power of 2 that way. This creates a logical explosion. The assumption that the sequence fills all gaps must be false.

Therefore, the sequence must keep skipping numbers forever.

The Speed Limit (The Upper Bound)

The paper doesn't just say "it skips numbers"; it also puts a speed limit on how fast the sequence grows.

Think of the sequence as a car.

• We know it's not driving at a constant speed (linear). It's accelerating.
• Tang proved that while it accelerates, it doesn't go too crazy. It won't reach "super-exponential" speeds (like $2^n$).
• He calculated a specific "speed limit" formula: The $n$-th number in the sequence is roughly less than $n^{1.66...}$.
• This is a huge step forward. Before this, we didn't even know if the sequence grew like a polynomial (a manageable curve) or something wilder. Now we know it's a "polynomial" growth, just a steep one.

Why Does This Matter?

This solves a 40-year-old mystery (Problem #423 on the Erdős Problems website). It tells us that even in simple, greedy games where you try to be as efficient as possible, chaos and gaps are inevitable. You can't force a perfect, gapless sequence just by adding neighbors together.

In a nutshell:
The Hofstadter sequence is like a greedy builder who tries to fill a wall with bricks. The builder is so eager to add the next brick that they skip over holes they can't fill. Tang proved that no matter how long the builder works, the wall will always have holes in it, and the builder will eventually be running so far ahead of the wall that the holes become a permanent feature of the landscape.

Technical Summary

Here is a detailed technical summary of the paper "The Hofstadter Consecutive-Sum Sequence Omits Infinitely Many Positive Integers" by Quanyu Tang.

1. Problem Statement

The paper addresses Problem 1.1, a long-standing open question regarding the asymptotic behavior of the Hofstadter consecutive-sum sequence (OEIS A005243).

• Definition: The sequence $(a_n)_{n \ge 1}$ is defined greedily:
  • $a_1 = 1, a_2 = 2$.
  • For $k \ge 3$, $a_k$ is the least integer strictly greater than $a_{k-1}$ that can be expressed as the sum of at least two consecutive earlier terms:
    $$a_k = \sum_{i=p}^q a_i \quad \text{for some } 1 \le p \le q \le k-1, \text{ with } q-p \ge 1.$$
• The Conjecture: Numerical evidence suggests the sequence contains "most" integers but omits specific values (e.g., 4, 7, 9, 12, 13, 15, 20...). Conjecture 1.2 (from OEIS) posits that the sequence omits infinitely many positive integers.
• Goal: Determine the growth rate of $a_n$ and prove whether the set of omitted integers is infinite.

2. Methodology

The author employs a combination of combinatorial number theory, Diophantine analysis, and additive combinatorics. The proof is divided into two main parts: a qualitative lower bound and a quantitative upper bound.

A. Generalization and Qualitative Analysis (Sections 2–3)

The author generalizes the problem to arbitrary finite seeds $u = (u_1, \dots, u_s)$ and defines the "excess" sequence $b_n = a_n - n$.

• Monotonicity: It is shown that $b_n$ is non-decreasing for $n \ge s$.
• Contradiction via Diophantine Equations:
  • The proof proceeds by contradiction: assume $b_n$ is bounded. This implies $a_n$ eventually becomes linear ($a_n = n + B$).
  • If $a_n$ is linear, the set of representable sums (sums of consecutive terms) eventually consists of sums of consecutive integers.
  • The author analyzes the representation of large powers of 2 (which must appear in the sequence if it omits infinitely many numbers, or conversely, if the sequence is linear, powers of 2 must be representable).
  • Using Lemma 2.1, a number is a sum of consecutive integers iff it is not a power of 2.
  • The structure of the sums leads to an equation of the form $v^2 + v + E = 2^k$.
  • By invoking the Schinzel-Tijdeman theorem (Lemma 2.2), which states that equations of the form $y^k = P(x)$ have finitely many solutions for $k > 2$, the author derives a contradiction. The equation $v^2 + v + E = 2^k$ cannot have infinitely many solutions.
  • Conclusion: The assumption that $b_n$ is bounded is false; thus, $b_n \to \infty$.

B. Quantitative Upper Bound (Section 4)

To establish an upper bound for the classical sequence ($u=(1,2)$), the author utilizes tools from additive combinatorics.

• Convexity of Prefix Sums: Let $s_m = \sum_{i=1}^m a_i$. The set of prefix sums $\mathcal{S}_m = \{s_0, \dots, s_m\}$ is shown to be a convex set (consecutive differences are strictly increasing).
• Difference Sets: The set of representable sums $R_m$ is related to the difference set $\mathcal{S}_m - \mathcal{S}_m$.
• Bloom's Theorem: The author applies a recent result by Bloom (Theorem 4.6) regarding the size of difference sets of finite convex sets:
  $$|A - A| \ge c_\eta |A|^{6681/4175 - \eta}$$
  for any finite convex set $A$.
• Recursive Argument:
  • The size of the set of representable integers $|R_m|$ is bounded below by a power of $m$.
  • Since $a_n$ is the greedy enumeration of $R$, a lower bound on $|R_m|$ translates to an upper bound on $a_n$.
  • This yields a recursive inequality of the form $a_n \le C n^\alpha a_{\lceil C n^\alpha \rceil}$.
  • Iterating this recursion (Lemma 4.9) leads to a polynomial upper bound.

3. Key Contributions and Results

Theorem 1.4 (Qualitative Result)

For any finite seed of positive integers, the sequence $b_n = a_n - n$ is unbounded and eventually non-decreasing.

• Corollary 1.5: $a_n = n + \omega(1)$.
• Significance: This proves Conjecture 1.2: The sequence omits infinitely many positive integers. The number of omitted integers up to $a_n$ grows to infinity.

Theorem 1.6 (Quantitative Result)

For the classical sequence, for every $\epsilon > 0$, there exists a constant $C_\epsilon$ such that:
$$a_n \le C_\epsilon n^{4175/2506 + \epsilon}$$

• The exponent $4175/2506 \approx 1.666$.
• This provides the first polynomial upper bound for the growth of the Hofstadter consecutive-sum sequence.

4. Significance and Discussion

• Settling the OEIS Conjecture: The paper definitively resolves the conjecture that the sequence omits infinitely many integers, a question that had remained open since Hofstadter's original inquiry.
• Generalization: The qualitative result applies to any finite seed of positive integers, not just $(1, 2)$.
• Methodological Innovation: The paper bridges the gap between self-generating sequences and modern additive combinatorics (specifically convex difference sets). The use of Bloom's bound on convex sets is a novel approach to this specific type of greedy sequence.
• Gap in Bounds:
  • Lower Bound: $a_n \ge n + \omega(1)$ (implies $a_n$ grows slightly faster than linear).
  • Upper Bound: $a_n \ll n^{1.666}$.
  • The author notes a substantial gap between these bounds. Numerical experiments (Section 5) suggest the true growth might be much closer to linear, potentially $a_n \approx n + n^{1/3}$, though this remains unproven.
• Future Directions: The author suggests that if the conjecture $|A-A| \gg |A|^{2-o(1)}$ for convex sets holds, the method could yield $a_n \le n^{1+o(1)}$, but even then, proving strict linearity ($a_n \sim n$) remains difficult with current techniques.

In summary, Tang's paper provides a rigorous proof that the Hofstadter consecutive-sum sequence is sparse (omitting infinitely many integers) and establishes a concrete polynomial upper bound for its growth rate, utilizing deep results from Diophantine equations and additive combinatorics.