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 \[ \frac npHence 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\), \(hh\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.

| interval | exact minimum of \(A(n)\) | first \(n\) | maximizing \(m\) |

|---:|---:|---:|---:|

| \([19{,}381,10^7]\) | 1 | 22,998 | \(22,999=109\cdot211\) |

| \([32{,}489,10^7]\) | 3 | 267,380 | \(267,383=47\cdot5689\) |

| \([267{,}381,10^7]\) | 21 | 267,436 | \(267,457=71\cdot3767\) |

| \([267{,}449,10^7]\) | 67 | 348,942 | \(349,009=421\cdot829\) |

| \([10^6,10^7]\) | 227 | 1,094,232 | \(1,094,459=739\cdot1481\) |

The last row in particular proves the concrete finite statement

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

[d] Million-block minima.

| block | minimum | first \(n\) | witness \(m\) |

|---:|---:|---:|---:|

| \(1{,}000{,}000\)–\(1{,}999{,}999\) | 227 | 1,094,232 | 1,094,459 |

| \(2{,}000{,}000\)–\(2{,}999{,}999\) | 523 | 2,011,360 | 2,011,883 |

| \(3{,}000{,}000\)–\(3{,}999{,}999\) | 595 | 3,175,752 | 3,176,347 |

| \(4{,}000{,}000\)–\(4{,}999{,}999\) | 835 | 4,071,942 | 4,072,777 |

| \(5{,}000{,}000\)–\(5{,}999{,}999\) | 877 | 5,266,180 | 5,267,057 |

| \(6{,}000{,}000\)–\(6{,}999{,}999\) | 1,117 | 6,427,572 | 6,428,689 |

| \(7{,}000{,}000\)–\(7{,}999{,}999\) | 1,119 | 7,289,750 | 7,290,869 |

| \(8{,}000{,}000\)–\(8{,}999{,}999\) | 1,037 | 8,470,542 | 8,471,579 |

| \(9{,}000{,}000\)–\(9{,}999{,}999\) | 1,379 | 9,893,094 | 9,894,473 |

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;

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

mathematically possible \(d\);

4. trial-divides the prime factors in every displayed certificate;

5. asserts the complete-table digest and every displayed block/tail value;

6. 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.