Erdoes #382 - working report - Erdős Problem a Day

Erdős problem 382 — wave 9a

Access/search date: 2026-07-28 UTC.

Claim labels

[A] elementary-rigorous: proved here from elementary facts or certified by complete factorizations.
[B] rigorous modulo named theorem: depends on the cited theorem/paper.
[C] plausible/structural-unverified: heuristic or a proposed route, not a theorem.
[D] computational-only: an exhaustive finite computation, with reproducible code, but no assertion beyond its finite range.

0. Mandatory live-page check

I fetched the live problem page and its discussion through the Bright Data browser path, rather than datacenter curl.

Live-page gate:

Status: OPEN.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
“Likes this problem”: None.
The other displayed markers (“looks difficult”, “looks tractable”,

formalisation interest) are also None.

Formalised statement: No.
Related OEIS sequence: A388850.
There is one comment, described below.

Thus the requested stop condition did not fire.

Verbatim current statement

Let $u\leq v$ be such that the largest prime dividing $\prod_{u\leq m\leq v}m$ appears with exponent at least $2$. Is it true that $v-u=v^{o(1)}$? Can $v-u$ be arbitrarily large?

Source: live problem 382 and its LaTeX view.

Everything else listed on the live page

The page reports the following.

[B] Erdős and Graham say that Ramachandra's results imply

$v-u\leq v^{1/2+o(1)}$.

[B, conditional] Cambie observes that the first question follows

from the old prime-gap conjecture that, for every $\epsilon>0$, every sufficiently large $u$ has a prime between $u$ and $u+u^\epsilon$.

[C] For the second question, the page gives the smooth-number

heuristic that a number near $q^2$ has largest prime factor below $q$ with “probability” $1-\log 2>0$. It therefore heuristically expects arbitrarily long runs of $q$-smooth integers around $q^2$. It points to problems 383 and 380.

Unverified page comment: Stijn Cambie, 08:47 on 11 Aug 2025, gives

\[ [17952448643078,17952448643091] \] of width $13$, saying that the largest prime is $4237033$ with multiplicity $2$. The same comment gives \[ [9419732244806055,9419732244806060], \qquad 9419732244806055=211193^3-2, \] of width $5$, saying that the largest prime has multiplicity $3$. The site explicitly warns that comments are not verified.

The browser also inspected the revision history; the current displayed mathematical text is the text above.

1. Literature check

Primary sources actually inspected

Erdős and Graham, *Old and new problems and results in combinatorial

number theory* (1980), scan, p. 73. The scan defines these as “bad” intervals. It states the stronger historical bound $v-u\leq v^{1/2-\epsilon}$ for some positive constant $\epsilon$, attributes this to Ramachandra, and conjectures both $v^\epsilon$ for every $\epsilon>0$ and arbitrarily large widths. [B]

K. Ramachandra, A Note on Numbers with a Large Prime Factor,

J. London Math. Soc. (2) 1 (1969), 303–306, DOI 10.1112/jlms/s2-1.1.303. The bibliographic record and DOI were verified. The Wiley PDF returned HTTP 403 in this environment, so I did not independently audit its proof. Its consequence for this problem is independently reported by both the Erdős–Graham primary source and the Tao paper below.

Terence Tao, Products of consecutive integers with unusual anatomy,

arXiv:2603.27990v2, submitted 30 Mar 2026 and revised 22 Apr 2026. This paper was not yet mentioned in the live problem text. Its Definition 1.2(i) is exactly the present notion of a bad interval. Theorem 1.7 proves an asymptotic counting result for integers lying in bad intervals, but Remark 6.2 explicitly says that it makes no progress on the two present conjectures. It identifies the obstruction as the lack of sufficiently strong upper bounds for the interval length $H$ or its largest prime $p_0$. [B]

The exact-phrase/title searches also found the current OEIS A388850 entry, which supplies upper bounds for widths 9–12, and no later claimed solution. This is an honest search miss, not a proof that no other literature exists. In particular, the live page remains the authority for the OPEN status.

What Tao's new theorem does and does not say

Let $\mathcal B$ be the integers contained in some bad interval and $\mathcal B^1$ the integers individually divisible by the square of their largest prime factor. Tao proves

\#(\mathcal B\cap[1,x])\sim\#(\mathcal B^1\cap[1,x]) =\frac{x}{\exp((\sqrt2+o(1))\sqrt{\log x\log\log x})}.

This settles a density conjecture associated to problem 380. [B] It does not control the maximum length of a connected bad interval: the asymptotic may be dominated by singleton intervals. [A] It therefore implies neither assertion in problem 382.

2. Exact elementary finite criterion

For $n>1$, define

L(n)=\max\{p:p\mid n\},\qquad E(n)=v_{L(n)}(n),

and put $L(1)=1,E(1)=0$. For a finite interval $I$, set

P_I=\max_{n\in I}L(n).

Then

v_{P_I}\left(\prod_{n\in I}n\right) =\sum_{\substack{n\in I\\L(n)=P_I}}E(n). \tag{1}

Proof: a number is divisible by $P_I$ exactly when its largest prime factor is $P_I$; no number in the interval has a larger prime factor. Adding valuations over a product gives (1). [A]

Consequently, $[u,v]$ is bad if and only if the right side of (1) is at least $2$. No huge product needs to be formed. [A]

3. Exact fixed-width computation

Define the literal fixed-width quantity

U_w=\min\{u\geq1:[u,u+w]\text{ is bad}\}.

This is not quite A388850: that sequence asks for the first maximal run of exactly width $w$. A subinterval of a wider maximal run is allowed in $U_w$, as it is in the statement of problem 382.

Exact first starts for widths 0–8

The scanner exhausted every earlier interval and obtained:

| width $w$ | exact $U_w$ | endpoint | largest prime | its exponent | |---:|---:|---:|---:|---:| | 0 | 4 | 4 | 2 | 2 | | 1 | 8 | 9 | 3 | 2 | | 2 | 48 | 50 | 7 | 2 | | 3 | 1680 | 1683 | 41 | 2 | | 4 | 76725 | 76729 | 277 | 2 | | 5 | 332925 | 332930 | 577 | 2 | | 6 | 4541155 | 4541161 | 2131 | 2 | | 7 | 4541154 | 4541161 | 2131 | 2 | | 8 | 75047565 | 75047573 | 8663 | 2 |

Each minimality assertion in this table is [D]. The finite test used for each interval is equation (1), whose correctness is [A].

The width-6 distinction is a useful audit: A388850 has $7474752$ as the first maximal run of exactly width 6, whereas the literal first width-6 bad interval is the subinterval $[4541155,4541161]$ of the first width-7 run.

Width 9: a finite lower bound and explicit upper bound

The final run tested all $999999991$ windows $[u,u+9]$ satisfying $u+9\leq10^9$. None is bad. [D] Separately, complete factorisation certifies that

\[ [4928180396,4928180405] \]

is bad: its largest prime is $70201$, and

\[ 4928180401=70201^2. \]

Every other prime in all ten integers is smaller than $70201$. [A] Thus the rigorously delimited finite bracket is

\boxed{999999992\leq U_9\leq4928180396}. \tag{2}

The lower inequality is [D] and the upper inequality is [A].

Explicit certified intervals of widths 9–13

The OEIS upper bounds and the live-page example were all factored again from scratch:

| width | $u$ | $v$ | largest prime $q$ | squared anchor $q^2$ | offset $q^2-u$ | |---:|---:|---:|---:|---:|---:| | 9 | 4928180396 | 4928180405 | 70201 | 4928180401 | 5 | | 10 | 40533366231 | 40533366241 | 201329 | 40533366241 | 10 | | 11 | 111460496439 | 111460496450 | 333857 | 111460496449 | 10 | | 12 | 436502026483 | 436502026495 | 660683 | 436502026489 | 6 | | 13 | 17952448643078 | 17952448643091 | 4237033 | 17952448643089 | 11 |

For every row, every integer in the interval factors completely over primes at most $q$, and $q^2$ is present. Hence every row is a rigorous explicit bad interval. [A]

The other live-page comment is also correct:

\[ 9419732244806057=211193^3, \]

and every integer in $[9419732244806055,9419732244806060]$ factors over primes at most $211193$. The largest prime therefore has total exponent $3$. [A]

These certificates prove existence only for the displayed finite widths; they do not prove unboundedness.

4. Re-verification code and independent audits

Standalone checker: erdos382_wave9a_reverify.py.

Run the full check from the repository root:

python runs/erdos382_wave9a_reverify.py --brief

The script is self-contained apart from a standard C compiler. Its SHA-256 is

8bb713635a733c43d953bfd811c39c7a36088fa9f24e26e3b460103da4e40a0f

It performs four audit layers:

A C scanner factors every integer in blocks of $2^{20}$ by segmented

trial division and computes $L(n),E(n)$ exactly. [A]

A monotone-deque sliding maximum is checked against a literal direct

recomputation on every scanned window. The billion-endpoint run audited all $999999991$ windows with no disagreement. [D]

A separate ordinary smallest-prime-factor Python implementation agrees

with the C implementation for every width 0–9 through $100000$. [D]

Explicit intervals are factored by a separate Pollard-rho routine.

Discovery is not trusted: every alleged prime factor is certified by elementary trial division, and every factorisation is multiplied back to the original integer. [A]

Final comprehensive rerun:

wall time       162.04 s
user CPU        161.90 s
maximum RSS     24324 KiB
main width-9 scan time 149.614996 s
windows tested and directly audited 999999991
first_start     0  (no hit in the scanned range)

The full table and all six explicit certificates were reproduced in that same final run.

5. Clean structural reduction

Tao's Lemma 6.1 gives the following. Write a nontrivial bad interval as $\{N+1,\ldots,N+H\}$, where $H$ is the number of elements. If it lies near size $x$, then:

H\leq N,\qquad H<p_0\ll\sqrt{x},

where $p_0$ is the largest prime of the product; exactly one interval element has the form $p_0^2m$, $m$ is $p_0$-smooth, and every interval element is $p_0$-smooth. [B, Tao Lemma 6.1]

Thus arbitrary-width examples would follow from the following concrete smooth-block statement:

For every $k$, there are a prime $q$ with $q^2>k$ and an integer $0\leq a\leq k$ such that all $q^2-a,\ldots,q^2+(k-a)$ are $q$-smooth.

Indeed, that block contains $q^2$, so its largest prime is at most $q$ and occurs at least twice; because $q\mid q^2$, its largest prime is exactly $q$. [A]

The five certified rows of widths 9–13 have precisely this form. This is evidence for the reduction, not a uniform proof. [C]

Tao's Lemma 6.3 further shows that every long bad interval contains a comparable-length, power-of-two subinterval with its $p_0^2m$ element at an endpoint. [B] Therefore a proof may restrict to these normalised intervals up to a constant loss in length, but $m$ cannot currently be removed. The stronger Erdős–Graham proposal corresponds to $m=1$.

6. Exact wall

First question

The missing uniform input is a subpolynomial all-$x$ prime-gap (or sufficiently strong large-prime-factor) theorem:

\forall\epsilon>0\quad \text{every sufficiently large }x\text{ has a prime in }[x,x+x^\epsilon]. \tag{3}

The live-page argument shows that (3) implies $v-u=v^{o(1)}$. [B, conditional] Existing fixed-power short-interval estimates, including Ramachandra's $x^{1/2-c}$-type consequence, do not supply the quantifier “for every $\epsilon>0$”. A finite computation cannot supply that asymptotic uniformity.

Second question

For each unbounded $k$, one needs simultaneous smoothness of an entire block, not merely a square anchor. Even if compatible congruences $q^2+j\equiv0\pmod {r_j}$ are engineered by the Chinese remainder theorem, they force only one divisor of each shift; they do not force the remaining cofactors to be $q$-smooth or ensure that $q$ is prime. [A] The independence probability $1-\log2$ on the live page does not control the correlations between $k+1$ neighbouring shifts uniformly in $k$. [C] This is the exact missing construction/smooth-run lemma.

Tao's density theorem cannot bridge this gap because it counts the union of all bad intervals rather than bounding their component lengths.

Cost of extending only the finite scan

The audited scanner took $149.615$ CPU-seconds per $10^9$ endpoints. A linear extrapolation gives:

through the width-9 upper-bound endpoint $4.928\times10^9$:

about $737$ CPU-seconds $=0.205$ core-hours;

through the width-13 example at $1.795\times10^{13}$:

about $746$ core-hours, roughly US $\$37$ at US $\$0.05$/core-hour.

These are estimates, not runs. The latter scan would still prove only a finite statement, and it would not answer either asymptotic question.

PARTIAL: Explicit bad intervals are rigorously certified through width 13; exact first starts are computed for widths 0–8, and an audited exhaustive search gives $999999992\leq U_9\leq4928180396$, but neither $v-u=v^{o(1)}$ nor unbounded widths is proved.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger