Erdős problem #463 — wave5x report

Accessed 2026-07-26 UTC. The live page is <https://www.erdosproblems.com/463>.

Claim labels

• [a] elementary-rigorous: proved below from definitions.
• [b] rigorous-modulo-named-theorem: none of the new conclusions below

need an external theorem.

• [c] plausible/structural-unverified: heuristic or an assessment of the

present analytic barrier.

• [d] computational-only: exact only on the explicitly stated finite

range, with the adjacent checker.

Step 0: live-page gate

[d, live-page observation] I fetched the live page through the Bright Data browser path and inspected both the rendered full-page screenshot and the DOM. It says OPEN, 0 comments on this problem, and 0 claimed proofs for this problem. The rows “Interested in collaborating” and “Currently working on this problem” both say None. Thus none of the mandatory stop conditions applied.

Verbatim live statement

Is there a function \(f\) with \(f(n)\to\infty\) as \(n\to\infty\) such that, for all large \(n\), there is a composite number \(m\) such that \[ > n+f(n)<m<n+p(m)? > \] (Here \(p(m)\) is the least prime factor of \(m\).)

Material listed on the live page

[d, live-page observation] The page cites [ErGr80] and [Er92e]. Its only mathematical remark says that in [Er92e] Erdős considers

and asks whether

It then says “See also [385].” There are no listed comments, partial results, or proof claims.

The bibliography popups identify the references as:

• P. Erdős and R. Graham, *Old and new problems and results in

combinatorial number theory*, Monographies de L'Enseignement Mathématique (1980), MR 0592420.

• Pál Erdős, *Some Unsolved problems in Geometry, Number Theory and

Combinatorics, Eureka* (1992), 44–48.

Literature and source check

[d, verified source fact] A primary scan of P. Erdős, Many old and on some new problems of mine in number theory, Congressus Numerantium 30 (1981), 3–27, is available at <https://users.renyi.hu/~p_erdos/1981-09.pdf>. On printed page 13 it asks, in equivalent fixed-\(c\) language, whether for every \(c\) and every sufficiently large \(n\) there is a composite \(m>n+c\) with \(m-p(m)<n\). The same page defines

and proposes the stronger \(f(n,c)\to\infty\) for fixed \(c\). I checked the rendered scan rather than relying on OCR. The downloaded PDF had SHA-256 15f1c458a256c9a2bd5d6c288d101a71365ed77804cde1ada44c1b1b914d8ac5.

[a] The fixed-\(c\) question in that 1981 source is equivalent to the live question. One direction follows because any \(f(n)\to\infty\) eventually exceeds each fixed \(c\). Conversely, choose thresholds \(N_k\) for \(c=k\), make them increasing, and set

Then \(f(n)\to\infty\), and the fixed-\(k\) witness has distance greater than \(k>f(n)\) after harmlessly shifting the thresholds.

[d, search result] Exact-phrase searches for the fixed-\(c\) formulation, \(m-p(m)<n\), and the cited titles found the live transcription, the 1981 primary scan, and references back to the old problem, but no later paper claiming a resolution. I verified that the two cited works exist bibliographically. I did not find an openly accessible full scan of the 128-page [ErGr80] monograph or the relevant Eureka issue, so I do not claim to have checked their page images. This search miss is not evidence that no unindexed literature exists.

[d, related-source fact] The page cross-links problem #385. Terence Tao's 2024 analysis, <https://terrytao.wordpress.com/2024/08/19/erdos-problem-385-the-parity-problem-and-siegel-zeroes/>, identifies a rough-semiprime short-gap statement at scales \(x^{1/u}\), \(2<u<3\), and explains the parity/Siegel-zero obstruction. Tao states that the required worst-case semiprime gaps are beyond current bounds, even if one assumes RH. The reduction below independently shows why precisely the same kind of missing estimate would settle #463.

Exact reformulation

Define, with the maximum of the empty set set to \(0\),

[a] Put \(d=m-n\). Then

Consequently the live question is exactly

Indeed, a proposed \(f\) gives \(A(n)>f(n)\). Conversely, if \(A(n)\to\infty\), choose \(f(n)=A(n)/2\) and take a maximizing \(m\).

[a] Universal sharp upper bound. If \(d\) is admissible, then \(p(n+d)\geq d+1\). A composite number is at least the square of its least prime factor, so

Thus

[a] Infinite exact closed form. For every prime \(p\), take

Here \(p(m)=p>d\), so \(A(n)\geq p-1\). But

and the universal bound gives the reverse inequality. Therefore

This proves \(\limsup A(n)=\infty\) and shows that the \(\asymp\sqrt n\) upper scale is attained infinitely often. It does not provide the uniform lower bound required by the problem.

Semiprime parametrisation and the precise analytic wall

[a] Suppose an admissible \(m\) is a semiprime \(m=pq\), where \(p\leq q\) are primes. The two inequalities \(n<pq<n+p\) are equivalent to

Hence a semiprime witness is exactly a prime \(p\nmid n\) for which

is prime and \(q\geq p\). Its distance is

This isolates the needed correlation between the primality of \(p\) and of a moving quotient of \(n\).

[a] A concrete sufficient missing lemma. Fix any \(1/3<\theta<1/2\) and put \(h=\lceil n^\theta\rceil\). The following worst-case short-interval assertion would solve #463:

For every sufficiently large \(n\), the interval \((n+h,n+2h]\) contains a composite \(m\) with \(p(m)>2h\).

For such an \(m\), \(h<m-n\leq2h<p(m)\), so \(A(n)>h\to\infty\). Moreover this \(m\) must be a semiprime for large \(n\): three prime factors would make \(m>(2h)^3>n+2h\). Thus this is a rough-semiprime gap theorem with factors on scales between \(n^\theta\) and \(n^{1-\theta}\).

[c] This sufficient lemma is stronger than the original question: #463 may conceivably be solved at a slower, \(n\)-dependent scale using composites with three or more prime factors. It is nevertheless the exact missing statement for the standard fixed-power semiprime route. Tao's related analysis says current prime/semiprime gap machinery does not give this worst-case interval result; ordinary lower-bound sieves also cannot ensure that a rough survivor is composite rather than prime. This is the parity barrier, not a missing finite calculation.

Exact finite computation

[d] I computed every \(A(n)\) for

There are exactly 90 zeros. The final 20 are

Thus, computationally only, \(A(n)>0\) for \(19381\leq n\leq10^7\), and \(19380\) is the last failure in the computed range.

[d] Sharp nested tail minima.

The last row in particular proves the concrete finite statement

and equality occurs first at \(n=1{,}094{,}232\).

[d] Million-block minima.

The SHA-256 of the complete sequence \((A(1),\ldots,A(10^7))\), encoded as little-endian unsigned 32-bit integers, is 652ab07ef4a45ebfab65468ffb2d8494a82a63864b09ba85088d28126bc9b155.

Why the bulk algorithm is exact

[a] A composite \(m\) with least prime factor \(p\) contributes precisely to

and its score there is \(m-n\). At a fixed \(n\), maximizing the score is the same as taking the largest active \(m\). The program buckets each \(m\) at the left endpoint \(m-p+1\), then takes a prefix maximum.

[a] For a requested endpoint \(N\), searching through

is sufficient. Indeed, if an interval from \(m=N+t\) reaches some \(n\leq N\), then \(t+1\leq p(m)\leq\sqrt m\), whence \(t^2+t+1\leq N\).

The exact core is:

def compute_bulk(limit):
    search_limit = limit + math.isqrt(limit) + 3
    marked = bytearray(search_limit + 1)
    start_max = array("I", [0]) * (limit + 1)

    for p in range(2, math.isqrt(search_limit) + 1):
        if marked[p]:
            continue
        for m in range(p * p, search_limit + 1, p):
            if marked[m]:
                continue
            marked[m] = 1       # p is the least prime factor of m
            start = m - p + 1
            if start <= limit:
                start_max[start] = max(start_max[start], m)

    A = array("I", [0]) * (limit + 1)
    witness = array("I", [0]) * (limit + 1)
    furthest = 0
    for n in range(1, limit + 1):
        furthest = max(furthest, start_max[n])
        if furthest > n:
            A[n] = furthest - n
            witness[n] = furthest
    return A, witness

The complete standalone checker, including all reference tables and certificates, is runs/erdos463_wave5x_verify.py.

Reproduction and independent checks

Run:

python3 runs/erdos463_wave5x_verify.py

[d] On this VM the final run completed in 20.03 seconds with peak RSS 174,848 KB. It:

1. computes the full table with the endpoint-bucket sieve;
2. recomputes all \(10^7\) entries, including maxima and zeros, using a

separate smallest-prime-factor sieve and fresh buckets;

1. compares every \(n\leq20{,}000\) with direct trial division over every

mathematically possible \(d\);

1. trial-divides the prime factors in every displayed certificate;
2. asserts the complete-table digest and every displayed block/tail value;
3. checks the exact prime-square identity for all 446 primes in range, ending

with \[ p=3137,\quad n=9{,}837{,}633,\quad A(n)=3136,\quad m=9{,}840{,}769. \]

[d, cost estimate] The measured pure-Python scaling is approximately linear up to logarithmic sieve factors. A direct extension to \(10^8\) would be about 3–4 minutes and roughly 1.7 GB with this deliberately redundant checker; \(10^9\) would be around 30–40 minutes and 17 GB. Neither computation can prove the required uniform limiting statement, so I did not run them under the few-CPU-minute constraint.

Honest conclusion

[a+d] The work gives (i) an exact extremal reformulation, (ii) a sharp universal upper bound, (iii) the infinite closed form \(A(p^2-p+1)=p-1\), (iv) an exact independently recomputed table through \(10^7\), and (v) a clean rough-semiprime short-gap lemma that would settle the problem. It does not establish the uniform lower limit \(A(n)\to\infty\). The remaining obstruction is a worst-case short-interval almost-prime problem at sub-square-root length, where currently cited prime/semiprime gap and sieve machinery does not supply the needed composite rough survivor.

PARTIAL: proved the sharp identity A(p^2-p+1)=p-1 for every prime p and independently verified A(n)>=227 on 10^6<=n<=10^7; the uniform limit remains blocked by a worst-case rough-semiprime gap lemma.