Erdős problem #826 — wave w016

Audit and computation date: 2026-07-28 UTC.

The standalone standard-library verifier is runs/erdos826_wavew016_verify.py. This report does not claim to solve the infinitude question. It gives an exact sharp-constant census, an elementary \((q,2q-1)\) prime-pair obstruction for that sharp subproblem, a reduction to the precise probabilistic estimate missing from the current sieve method, and an audited account of the literature.

Claim labels used throughout:

• (a) elementary-rigorous;
• (b) rigorous modulo the explicitly named theorem;
• (c) plausible/structural-unverified;
• (d) computational-only, with the finite exhaustiveness proof stated

below.

0. Mandatory live-page audit

I fetched the Cloudflare-protected live page and its discussion thread through the Bright Data browser, not datacenter curl.

The state observed on 2026-07-28 was:

• status: OPEN;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• likes: None;
• “This problem looks difficult”: TerenceTao;
• “This problem looks tractable”: None;
• “The results on this problem could be formalisable”: None;
• “I am working on formalising the results”: None;
• formalised statement: Yes;
• last page edit: 17 April 2026.

Thus no required stop condition applied.

The following is the verbatim current statement from the site's LaTeX view:

Are there infinitely many \(n\) such that, for all \(k\geq 1\), \[ > \tau(n+k)\ll k? > \]

The page labels this a stronger form of problem #248. Its listed known result is that Lau [La26] proved the existence of an absolute \(C\) and infinitely many \(n\) for which

The bibliography entry is C. F. Lau, On the number of prime factors of consecutive integers, arXiv:2604.15042 (2026).

The two comments were also read:

1. Alfaiz, 17 April 2026, pointed out Lau's polynomial-bound result; the

comment now says that the site was updated in response.

1. Dogmachine, 26 August 2025, remarked that a solution, as with problem

#469, would bypass technical details in some proofs, but judged that prospect unlikely.

The page warns that comments are unverified. Neither comment claims a proof.

Authoritative links:

• <https://www.erdosproblems.com/826>
• <https://www.erdosproblems.com/latex/826>
• <https://www.erdosproblems.com/forum/discuss/826>

1. Results obtained

1.1 Exact sharp-constant census

Define

Since \(n+1\geq2\), one has \(\tau(n+1)\geq2\), and hence

Thus \(2\) is the smallest constant any individual \(n\) can attain. This observation is (a).

The exact exhaustive computation gives (d):

Equivalently, these ten and only these ten \(n\leq10^9\) satisfy

This is a finite result, not evidence that the list is complete over all positive integers. It also addresses the sharp constant \(2\), whereas Erdős #826 allows an unspecified absolute constant.

The canonical SHA-256 of the ASCII stream n\n formed from the increasing list in (1.2) is

2675f1d02d77ebd7ab6aa0593944694c3981674a2d49470d8804146f3b85fa0f

The decimal endpoint census is:

| \(X\) | survive \(k=1\) | survive \(k=1,2\) | satisfy all \(k\geq1\) | |---:|---:|---:|---:| | \(10\) | 5 | 4 | 4 | | \(10^2\) | 26 | 8 | 8 | | \(10^3\) | 168 | 23 | 9 | | \(10^4\) | 1,229 | 111 | 9 | | \(10^5\) | 9,592 | 674 | 9 | | \(10^6\) | 78,498 | 4,302 | 9 | | \(10^7\) | 664,579 | 30,741 | 10 | | \(10^8\) | 5,761,455 | 229,555 | 10 | | \(10^9\) | 50,847,534 | 1,774,614 | 10 |

Every row is (d). The first column after \(X\) is simply the number of primes \(n+1\) in the range, but it was recomputed rather than imported from a prime-count table.

Through \(10^8\), every non-solution has already failed by \(k=18\). The numbers surviving after all inequalities through each failure-bearing value of \(k\) are (d):

| inequalities imposed through \(k=\) | survivors \(n\leq10^8\) | |---:|---:| | 1 | 5,761,455 | | 2 | 229,555 | | 3 | 28,269 | | 4 | 2,010 | | 5 | 932 | | 6 | 125 | | 7 | 92 | | 8 | 49 | | 9 | 38 | | 10 | 21 | | 11 | 20 | | 12 | 12 | | 15 | 11 | | 18 | 10 |

There were no first failures at \(k=13,14,16,17\). The ten final survivors were nevertheless checked through their individual rigorous tail cutoffs; they were not accepted merely because they survived through \(18\).

For the largest value \(n=4,062,240\), the program checks through \(k=2016\) and the elementary tail bound below certifies every \(k\geq2017\). Direct trial factorisation finds equality \(\tau(n+k)=2k\) exactly at

within the checked range. These arithmetic facts are (d).

1.2 A \((q,2q-1)\) prime-pair obstruction for the sharp subproblem

The following reduction is (a).

Suppose \(\tau(n+k)\leq2k\) for every \(k\geq1\). At \(k=1\),

so \(p=n+1\) must be prime. At \(k=2\),

For \(p\geq11\), the even number \(p+1\geq12\) cannot be a prime, a prime square with at most three divisors, or a prime cube with four divisors: the only even instances of the latter two forms are \(4\) and \(8\). The remaining factorisation type having at most four divisors is a product of two distinct primes. Therefore

with \(q\) prime. Thus both \(q\) and \(2q-1=p\) must be prime.

Consequently,

The infinitude of such two-linear-forms prime pairs is itself unproved (it is predicted by the prime-tuples/Dickson heuristic). This does not say that Erdős #826 itself implies that prime-pair conjecture: #826 may use a constant larger than \(2\). Nor are these prime pairs sufficient for (1.3); at \(X=10^9\), 1,774,614 values survive the first two inequalities (the prime-pair cases plus the two small exceptional cases), but only ten survive all shifts. The implication is (a); the prediction of infinitude is (c).

2. Why the all-\(k\) finite checker is exhaustive

2.1 Rigorous tail cutoff

Divisors of an integer \(m\) pair as \(d,m/d\), with at most one unpaired square-root divisor. Hence

This is (a).

Put \(r=\lfloor\sqrt n\rfloor\). If \(k\geq r+2\), then

Thus \(n+k<k^2\), and (2.1) gives

It is therefore enough to test

This proves that the program's acceptance condition is exactly (1.3), not a heuristic finite window. The reduction (2.3) is (a).

2.2 Full divisor-table engine

For every \(m\) up to

the main engine constructs the smallest prime factor and then computes \(\tau(m)\) inductively. If \(m=pu\), then

Induction on \(m\), using the prime-power formula for \(\tau\), proves that the entire table is exact. The algorithmic argument is (a); its output is (d).

At \(X=10^7\), a second engine independently initialized a zero table and, for every divisor \(d\), added one to

Every divisor of every table entry is encountered exactly once, so this is another exact construction. The two arrays agreed entry-for-entry through

They then produced the same census and digest. This double computation took about 34 seconds.

2.3 Independent prime-pair/direct-factor engine

The range-efficient engine does not use the bulk recurrence (2.4).

1. An odd-only Eratosthenes sieve finds every prime \(p=n+1\).
2. The classification following (1.4) enumerates exactly the values surviving

\(k=2\): \(p=2q-1\) with \(q\) prime, together with \(p=2\) and the exceptional \(p=7\) for which \(p+1=8\).

1. Each remaining \(n+k\), from \(k=3\) through (2.3), is factored directly

using a separately generated list of primes up to the required square root.

Steps 1–3 are an exhaustive algorithm by the elementary arguments already given. This engine independently reproduced the ten-value list and digest through \(10^8\). It also supplied the single-engine exact extension through \(10^9\), examining all 1,774,614 survivors of \(k=1,2\). The \(10^9\) run used 89 CPU-seconds and peaked at 1.04 GB before a later no-copy count optimization; the mathematical search path was unchanged.

Selected endpoint solutions and every tested shift of the largest solution were additionally recomputed by a third one-value trial-division routine.

The independent scopes are therefore stated precisely:

• \(X=10^7\): two complete divisor tables, candidate engine, and selected

trial factorisations;

• \(X=10^8\): full factor table plus independent candidate/direct-factor

engine;

• \(X=10^9\): exact candidate/direct-factor engine, with regression checks

against the already double-verified ten-value stream.

3. Reproduction

The adjacent checker uses only the Python standard library:

# Complete independent divisor tables and candidate audit through 10^7.
python runs/erdos826_wavew016_verify.py \
  --limit 10000000 --engine both --candidate-audit

# Range-efficient exact all-k census through 10^9.
python runs/erdos826_wavew016_verify.py \
  --limit 1000000000 --candidate-only

The checker contains fixed regression counts and digests for \(10^7\), \(10^8\), and \(10^9\). They are assertions only and are never used to generate candidates.

For reference, the \(10^8\) full factor-table run took 97 CPU-seconds and about 701 MB peak RSS; its separately run candidate audit took 6.3 seconds. The full divisor-addition engine should not be requested at \(10^8\): its \(\sum_{d\leq X}X/d\) Python updates would exceed the stated few-minute budget.

A direct \(10^{10}\) extension with the present unsegmented candidate engine would require roughly 5 GB just for odd-prime flags and, extrapolating from the \(10^9\) run, about 0.3–0.5 core-hours. A segmented sieve would lower memory but not change the finite nature of the result, so it was not run.

4. Primary-source literature audit

4.1 Erdős's original question

The cited paper exists as P. Erdős, Remarks on some problems in number theory, Math. Balkanica 4 (1974), 197–202. On the problem-session page, Erdős and Straus ask first for an infinite sequence with \(v(n_k+i)<c_1i\), where their \(v\) counts distinct prime factors, and then ask whether an infinite sequence exists with \(d(m_k+i)<c_2i\), where the constants are absolute. The scan is:

<https://users.renyi.hu/~p_erdos/1974-27.pdf>.

This verifies both the attribution and the intended uniform implied constant. It also avoids the vacuous interpretation in which the constant could depend arbitrarily on \(n\).

4.2 Tao–Teräväinen

Tao and Teräväinen, Quantitative correlations and some problems on prime factors of consecutive integers, arXiv:2512.01739v2 (25 April 2026), prove that an absolute \(C\) and infinitely many \(n\) satisfy

This settles the weaker problem #248. Since

it yields only an exponential-in-\(k\) divisor bound. This statement is (b), and (4.1) is (a).

Primary source:

<https://arxiv.org/abs/2512.01739>.

4.3 Lau

Lau, On the Number of Prime Factors of Consecutive Integers, arXiv:2604.15042v2 (24 June 2026), proves (b)

for infinitely many \(n\) and an absolute \(C\). By (4.1),

for an absolute \(C'\), which is Corollary 1.2 of the paper. The printed corollary uses \(k\geq2\); the live page's \(k\geq1\) formulation follows elementarily by replacing \(n\) with \(n+1\):

Primary source:

<https://arxiv.org/abs/2604.15042>.

The current v2 really contains the claimed theorem and corollary; it is not merely an ID/title match.

4.4 Search miss

Exact-formula, exact-title, problem-number, forward-citation, and 2026 arXiv searches found no later primary source proving the linear divisor bound. The newest directly relevant primary item located was Lau v2. This is an honest search result, not a proof that no uncatalogued manuscript exists.

5. The exact remaining analytic gap

Lau's argument constructs a probability measure on \(n\in[x,2x]\) and proves, for sufficiently large \(C\),

The union bound then makes all the desired \(\Omega\)-events hold simultaneously. This is (b) from Proposition 5.1 of Lau v2.

For #826, the exact analogous missing input is a summable near-critical divisor-tail estimate. One sufficient statement would be:

There are absolute \(A,\delta>0\), a fixed \(\eta>0\), and, for all sufficiently large \(x\), a probability measure on \([x,2x]\) such that \[ > \Pr\!\left(\log\tau(\mathbf n+k)>\log k+\log A\right) > \leq c\,k^{-1-\delta} > \] uniformly for \(2\leq k\leq x^\eta\), with the sum of the right-hand sides (after adjusting \(A\)) strictly below \(1\).

The implication from this estimate to #826 is (a): apply the union bound, then use the standard uniform bound \(\tau(m)=m^{o(1)}\) for \(x^\eta<k\ll x\), and (2.1) once \(k\) is larger than \(x\). The uniform divisor bound is a named classical theorem, so this last middle-range step is (b).

What Lau currently controls is the coarser additive statistic \(\Omega=\sum_p\nu_p\). Forcing the goal merely through \(\tau\leq2^\Omega\) would require the essentially critical coefficient

Lau proves \(C\log k\) only for a sufficiently large \(C\); the reduction in his proof even takes \(C=12A+4C_1+1002\) after several concentration parameters have been made large. Thus current constants are not close to (5.2). Moreover, (4.1) is lossy on repeated prime powers, so the natural target is a high-moment or Laplace-transform estimate for

not just a smaller unspecified constant in an \(\Omega\)-bound.

Lau's Conjecture 5 predicts that, for every sufficiently large \(n\), some shift has

This is only conjectural, so it is (c), but it explains why the needed coefficient is a threshold rather than a routine constant optimization.

No finite search, including (1.2), supplies the uniform positive-probability estimate above. Conversely, the existing Maynard/Selberg sieve moment calculations in the audited papers do not provide it. This precise near-critical weighted concentration lemma is the analytic wall.

6. What is and is not established

• Established (a): the all-\(k\) cutoff (2.3), sharp lower constant \(2\),

prime-pair implication (1.5), and the exact form of the missing union-bound input.

• Established (b): Tao–Teräväinen's \(O(k)\) bound for \(\Omega\), Lau's

\(O(\log k)\) bound for \(\Omega\), and hence Lau's polynomial divisor bound.

• Established (d): the exact list (1.2) through \(10^9\), double-verified

through \(10^8\) and with two complete divisor tables through \(10^7\).

• Not established: infinitude for any absolute linear constant, finiteness

or infinitude of the sharp-constant list, or the missing near-critical divisor-tail estimate.

PARTIAL: exactly ten sharp-constant solutions \(n\leq10^9\), with a rigorous all-\(k\) checker and \((q,2q-1)\) prime-pair obstruction; #826 remains open at the near-critical \(\log\tau\) concentration lemma.