Erdős problem 423 — wave 9h

Access date: 2026-07-28 UTC.

Claim labels

Every mathematical claim below is labelled as requested:

• [a] elementary-rigorous;
• [b] rigorous modulo the explicitly named theorem/source;
• [c] plausible or structural but unverified;
• [d] computational-only.

Page-status and bibliographic facts are identified as such and linked to their sources rather than given a mathematical claim label.

0. Mandatory live-page check

I fetched the rendered live page and its full discussion thread through the Bright Data browser path, not by datacenter curl.

Verbatim live statement:

Let \(a_1=1\) and \(a_2=2\) and for \(k\geq 3\) choose \(a_k\) to be the least integer \(>a_{k-1}\) which is the sum of at least two consecutive terms of the sequence. What is the asymptotic behaviour of this sequence?

The live-page audit was:

• status: OPEN;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• comments: 38;
• page last edited: 23 March 2026.

Thus none of the mandatory stop conditions applied.

The page's incorporated known results say:

1. the sequence begins

\(1,2,3,5,6,8,10,11,\ldots\) and is OEIS A005243;

1. Bolan and Tang independently proved that, for

\(b_n:=a_n-n\), the sequence \(b_n\) is nondecreasing and unbounded;

1. Tang proved a polynomial upper bound using convex difference sets;

with Cushman's current exponent this is \[ a_n\ll n^{688/413+o(1)}\leq n^{1.6659+o(1)}; \]

1. Tang proved

\[ a_n=n+\Omega(\log\log n); \]

1. the page says that \(a_n=n+o(n)\) appears likely, but does not claim it.

I read the full thread rather than only the incorporated summary. The mathematically relevant comment groups are: Tang's March 2026 paper and the statement that even \(a_n=O(n)\) remains unknown; the Cushman-exponent update and its correction/recheck; Bolan's independent omission proof and quadratic upper-bound argument; the \(n\leq 30000\) numerical experiment; the much larger posted complement counts; and the empirical concentration of holes in classes divisible by large powers of two. None of the comments claims a solution, and the modular patterns are presented as questions/experiments, not theorems.

Authoritative live source: Erdős Problems #423 and its discussion thread.

1. Primary-source literature check

Exact-title, problem-number, and OEIS-number searches found one directly relevant arXiv paper:

• Quanyu Tang,

The Hofstadter consecutive-sum sequence omits infinitely many positive integers, arXiv:2603.09939v2 [math.NT], revised 23 March 2026. I downloaded and read the 16-page v2 PDF; its SHA-256 is 0ca63f8c662233b1cf77005a64745ffcbd3d37d439dd9635940d43977d4b2711. Theorem 1.4 gives the more precise lower bound \[ a_n\geq n+\frac{\log\log n}{\log 20}-O(1), \] and Theorem 1.5 gives \(a_n\leq C_\varepsilon n^{4175/2506+\varepsilon}\). [b: Tang, Theorems 1.4 and 1.5, using Beukers and Bloom respectively]

Tang's Section 6.2 records the later improvement obtained from:

• Adam Cushman,

A Note on the Sum-Product Problem and the Convex Sumset Problem, arXiv:2512.13849v2 [math.CO]. I downloaded and checked Theorem 1.5 in the v2 PDF; its SHA-256 is 216b73c9d81292c55b58242f6efa9581c2fa0c9f5429bfb667d4d9bbed1bdf15. It states, for finite convex \(A\), \[ |A-A|\gg_\varepsilon |A|^{8/5+1/3440-\varepsilon}. \] [b: Cushman, Theorem 1.5]

The exponent conversion is exact:

[a] The checker recomputes this with fractions.Fraction, as well as \(1/(6681/4175-1)=4175/2506\).

I also checked the current A005243 and its complement A048973. Broader “Hofstadter sequence” searches mostly return the unrelated \(Q\), \(H\), or figure-figure sequences. I found no other directly relevant arXiv paper, nor a post-23-March-2026 primary source proving a linear bound or determining the asymptotic. A non-arXiv search hit making much stronger formula language was not used as evidence. The original sources cited by the live page are Erdős (1977), p. 71, and Erdős--Graham (1980), p. 83; the live page remains the authority for the exact formulation in this run.

2. An elementary reduction for the holes

Let

2.1 The greedy sequence enumerates every block sum

Let \(\mathcal R\) be the set of sums of blocks of at least two consecutive terms of \(A\). Then

[a]

Indeed, every \(a_k\), \(k\geq3\), is in \(\mathcal R\) by definition. Conversely, take \(t\in\mathcal R\). All terms in a positive block summing to \(t\) are strictly below \(t\). If the increasing sequence jumped from a term below \(t\) to a term above \(t\), that block would already be available at the jump, contradicting the greedy choice. Hence \(t\) is eventually selected. This is a from-scratch version of Tang's Lemma 5.1.

2.2 Interval-hitting lemma

If a hole \(N\in\mathcal H\) has an ordinary consecutive-integer representation

then

[a]

Otherwise every integer \(u,u+1,\ldots,v\) belongs to \(A\). As they are consecutive integer values, they occur consecutively in the increasing sequence \(A\); their sum would put \(N\) in \(\mathcal R=A\setminus\{1,2\}\), a contradiction.

This applies simultaneously to every positive consecutive-integer representation of a hole, not only to one chosen representation. [a]

2.3 A canonical descent forest

Write

and suppose \(N\) is not a power of two. Put

Then \(u(N)\) is a positive integer and

[a]

There are two cases. If \(q<2^{k+1}\), then \(L=q\) and the block is centred at \(2^k\). If \(q>2^{k+1}\), then \(L=2^{k+1}\) and \(u=(q-L+1)/2\). (Equality is impossible because \(q\) is odd and \(2^{k+1}\) is even.) Direct substitution gives the displayed sum in both cases. The block has at least two terms and its right endpoint is below \(N\).

Combining this representation with the interval-hitting lemma gives:

Every non-power-of-two hole \(N\) has an earlier hole in its explicitly computable canonical interval \[ > I(N)=[u(N),u(N)+L(N)-1]. > \]

[a]

Iterating produces a well-founded directed forest on the holes, and every root is a power of two which is itself a hole. [a] This gives a rigorous explanation for why powers of two and 2-adic structure naturally appear in the numerical data; it does not prove the empirical modular-finiteness questions from the comments.

2.4 Exact counting consequence, and why it is not enough

Fix \(k\geq0\), put \(L=2^{k+1}\), and consider holes \(N=2^kq\leq X\) with \(q\geq L+1\) odd. Their canonical interval is

If a given earlier hole \(h\) lies in this interval, then

which allows at most \(L\) odd values of \(q\). Also

Consequently, if \(H_k(X)\) counts holes at most \(X\) with exact 2-adic valuation \(k\), then

[a] The final \(L/2\) covers the power-of-two case and the finitely many odd parts \(q<L\).

Equation (2.1) is the precise wall for this descent argument. If hypothetically \(H(y)\sim\delta y\), its main right-hand term is \(\delta X\): the at-most \(L\)-to-one parent assignment loses exactly the scale contraction by \(L\). Thus (2.1) is density-neutral and cannot by itself prove \(H(X)=o(X)\). [a]

A usable next lemma would have to give a strict average multiplicity saving over this worst-case \(L\)-to-one assignment, uniformly enough to sum over \(k\), or exploit the simultaneous hitting constraints from the other odd divisors of \(N\). No such saving follows merely from interval hitting: dense sets of putative holes satisfy that necessary condition too. [a] This is the exact missing combinatorial ingredient in this route.

Finally,

[a] At \(x=a_n\), \(H(a_n)=a_n-n\). Conversely, if \(a_n=n+o(n)\) and \(a_n\leq x<a_{n+1}\), then \(H(x)=x-n=o(x)\). This identifies exactly what the missing multiplicity lemma would need to deliver.

3. Exact finite computation

The standalone verifier is erdos423_wave9h_reverify.py. It uses only the Python standard library.

3.1 Exact sieve invariant

The main loop is:

is_term[1] = is_term[2] = 1
terms = array("I", [1])
for value in range(2, limit + 1):
    if not is_term[value]:
        continue
    block_sum = value
    for previous in reversed(terms):
        block_sum += previous
        if block_sum > limit:
            break
        is_term[block_sum] = 1
    terms.append(value)

When value is accepted, the loop marks exactly the new block sums ending in that term. All terms are positive, so every mark is larger than value and is made before the increasing scan reaches it. Induction on value proves that the bit table is exact through the cutoff. [a]

For independence, the verifier also:

1. applies the literal greedy definition with a separate positive

sliding-window search through value 4000 and compares all membership bits;

1. checks the displayed OEIS prefix through 100;
2. reconstructs every ordinary consecutive-integer representation of every

computed hole from its odd divisors and checks the interval-hitting lemma;

1. checks the exponent arithmetic with exact rational numbers.

3.2 Verified table

Let \(H(X)\) denote the number of holes at most \(X\). The full run gave:

| \(X\) | \(H(X)\) | \(X-H(X)\) | |---:|---:|---:| | \(2^{10}=1,024\) | 143 | 881 | | \(2^{11}=2,048\) | 183 | 1,865 | | \(2^{12}=4,096\) | 238 | 3,858 | | \(2^{13}=8,192\) | 298 | 7,894 | | \(2^{14}=16,384\) | 371 | 16,013 | | \(2^{15}=32,768\) | 461 | 32,307 | | \(2^{16}=65,536\) | 555 | 64,981 | | \(2^{17}=131,072\) | 689 | 130,383 | | \(2^{18}=262,144\) | 849 | 261,295 | | \(2^{19}=524,288\) | 1,059 | 523,229 | | \(2^{20}=1,048,576\) | 1,308 | 1,047,268 | | \(2^{21}=2,097,152\) | 1,637 | 2,095,515 | | \(2^{22}=4,194,304\) | 2,056 | 4,192,248 | | \(2^{23}=8,388,608\) | 2,610 | 8,385,998 | | \(2^{24}=16,777,216\) | 3,326 | 16,773,890 | | \(2^{25}=33,554,432\) | 4,302 | 33,550,130 |

[d] These independently reproduce the live-thread counts through the range checked. Since \(2^{25}\) is a term, the endpoint identity is

[d]

The portable SHA-256 of the comma-separated complete list of 4,302 holes is

37b6b4d47b94a4f5306a494140c0387ae34e07aa5abb9819493ca0bb8fab2264

[d]

All nonsingleton runs of holes through \(2^{25}\) are exactly

[d] In particular, every hole from 396 through \(2^{25}\) is isolated from the other holes. [d] This is a finite statement only; it does not answer the thread's question about whether twin or triple gaps recur.

Further exact checks:

• the only power-of-two holes through \(2^{25}\) are

\(4,64,128,4096\); [d]

• assigning each non-root hole to the least hole in its canonical interval

yields root-tree sizes \(4182,1,70,49\), respectively, and maximum depth 11; [d]

• all 6,664 nontrivial ordinary consecutive-integer representations of the

4,302 holes hit an earlier hole, as the lemma requires; [d]

• there are 108 odd holes through the cutoff, the last being 28,396,673;

hence the data do not support claiming that odd holes have already stopped; [d]

• the largest spacing between consecutive holes in the checked range is

206,016, between 26,540,608 and 26,746,624. [d]

The full invocation

/usr/bin/time -f 'wall=%e sec maxrss=%M KB' \
  python3 runs/erdos423_wave9h_reverify.py

ended with ALL CHECKS PASSED, taking 54.93 seconds wall time and 181,956 KB maximum resident memory on this VM. A quick independent regression is available with --quick.

4. Honest endpoint

No closed form, counterexample, linear upper bound, or asymptotic is proved here. The rigorous new output is the explicit hole-descent/interval-hitting reduction and its density-neutral recurrence (2.1); the computational output is an independently checked exact regime through \(2^{25}\), including a complete run classification and certificate hash.

The present sieve uses \(\Theta(X)\) storage and, for a near-identity sequence, about \(\Theta(X\log X)\) generated block events. [a: operation count for this algorithm] Extrapolating the measured run naively from \(2^{25}\) to the discussion's \(2^{37}\) scale gives roughly 90--100 single-core hours and about 0.7 TB for the byte table plus 32-bit term array; that heavier run was not attempted. [c: engineering extrapolation] More computation would extend finite evidence, but it cannot supply the uniform multiplicity saving needed after (2.1).

PARTIAL: Proved an elementary canonical descent forest and density-neutral recurrence for all holes; independently verified exactly 4,302 holes and all gap runs through \(2^{25}\), but the uniform multiplicity saving needed for \(a_n=n+o(n)\) remains open.