Erdős problem #1073 — wave 8c
Date of audit and computation: 2026-07-28 (UTC).
Claim labels used below:
- (a) elementary-rigorous: proved here from elementary facts.
- (b) rigorous modulo named theorem: the dependency is named.
- (c) plausible/structural-unverified: heuristic or an unproved route.
- (d) computational-only: certified finite computation or a document/search audit.
0. Mandatory live-page audit
I fetched both the rendered problem page and its LaTeX view through the Bright
Data browser, rather than relying on the supplied tracker YAML.
The exact current statement is:
> Let \(A(x)\) count the number of composite \(u Source: live page and (d) Page status. The page says OPEN. It displayed: Thus none of the mandated stop conditions was present. (d) Context actually listed on the page. It gives the initial values \(25,121,169,437,\ldots\), links OEIS A256519, recalls Wilson's theorem, cites Hardy–Subbarao, and says the question occurs in Guy's problem A2. It lists no partial bound. 1. (d) G. E. Hardy and M. V. Subbarao, “A Modified Problem of Pillai and Some Related Questions”, American Mathematical Monthly 109 (2002), 554–559, DOI 10.1080/00029890.2002.11919885, exists and was read. Its Problem F on p. 557 is the source of this question. It gives \(25,121,721\) as examples but supplies no bound for \(A(x)\). 2. (d) Richard Guy's third-edition Unsolved Problems in Number Theory exists; “Prime Numbers” is the chapter containing A2. The live Erdős page identifies A2 as a mention of this question. I did not have the chapter text needed to attribute any stronger statement to Guy. 3. (d) OEIS A256519 has the equivalent definition and a 719-entry b-file ending at \(99\,795\,337\). It is sequence data, not a proof of an asymptotic assertion. 4. (d) Exact-title, exact-congruence, DOI-citation, and sequence searches found no later primary paper specifically proving a bound for this \(A(x)\). OpenAlex's citation record for the 2002 paper showed only Guy's 2004 “Prime Numbers” chapter. This is an honest search result, not a theorem that no such literature exists. 5. (b) The adjacent paper of Klurman and Munsch, “Distribution of factorials modulo \(p\)” (journal version here), concerns the number of residue classes occupied or missed by \(n!\bmod p\). Its one-modulus set-size results do not give an upper bound for occurrences of the particular residue \(-1\), much less correlations of that occurrence for two different primes. I therefore do not use it as if it solved the required counting problem. Write \(P^-(u)\) for the least prime divisor of \(u>1\). (a) If \(u\mid n!+1\), then every prime divisor of \(u\) is greater than \(n\). In particular,
1. Source and literature audit
2. Elementary exact reductions
Lemma 1
\(p\mid n!+1\), which is impossible. \(\square\)
Lemma 2: finite search identity
(a) If \(u
therefore terminates at \(n=s-1\).
Lemma 3: how to enumerate without factoring a huge factorial
Fix \(n dividing \(N\). (a) If no such \(p\) exists, \(N\) has no composite divisor below \(X\). If it exists, every prime \(q\) occurring in any composite divisor \(d \(N\) obeys Proof. A composite \(d Removing one prime factor from \(d\) shows every other prime factor is at most \((X-1)/r\leq(X-1)/p\); the same argument inside \(N\), which is also divisible by \(p\), gives \(q\leq N/p\). The least factor itself also satisfies these bounds whenever a composite divisor is possible. \(\square\) Now is precisely the squarefree product of all relevant prime divisors. Exact division recovers their valuations, after which ordinary divisor generation recovers every \(d most 4096 primes so it never has to factor \(N\) or hold one enormous global primorial. Core executable logic: The full standard-library-only implementation is This does not reach the requested subpolynomial bound, but it is a rigorous uniform estimate. (a) As \(x\to\infty\), In particular, \(A(x)=o(x)\). Let \(L=\log x\), \(\ell=\log\log x\), and, for sufficiently large \(x\), put First discard the fewer than \(\sqrt x\) possible \(u<\sqrt x\). Suppose \(\sqrt x\leq u for all sufficiently large \(x\). This contradicts \(u\leq n!+1\) and \(u\geq\sqrt x\). Hence \(n\geq y\). Lemma 1 now says that \(u\) has no prime divisor at most \(y\). Let \(P(y)=\prod_{p\leq y}p\). Full inclusion–exclusion gives \(2^{\pi(y)}\) squarefree divisors of \(P(y)\). The finite Euler product contains \(1/k\) for every \(1\leq k\leq y\), so Also \(2^{\pi(y)}\leq2^y=x^{o(1)}\). Equations (4)–(5) therefore yield the fully explicit intermediate bound Since \(\log(y+1)=(1+o(1))\log\log x\), (3) follows. \(\square\) (a) For every prime \(p\geq5\), is a distinct composite member of the set, witnessed by \(n=p-1\): Wilson's theorem gives \(p\mid u_p\), while \(u_p>p\). (b) Stirling's formula and the prime number theorem therefore give This is consistent with \(x^{o(1)}\) and is not a counterexample. All counts here use the problem's strict convention \(u (d) The complete enumeration gives: | \(X\) | exact \(A(X)\) | |---:|---:| | \(10\) | 0 | | \(10^2\) | 1 | | \(10^3\) | 7 | | \(10^4\) | 28 | | \(10^5\) | 60 | | \(10^6\) | 131 | | \(10^7\) | 290 | | \(10^8\) | 719 | | \(1.1\cdot10^8\) | 754 | | \(1.2\cdot10^8\) | 779 | | \(1.3\cdot10^8\) | 808 | | \(1.4\cdot10^8\) | 825 | | \(1.5\cdot10^8\) | 850 | | \(1.6\cdot10^8\) | 879 | | \(1.7\cdot10^8\) | 902 | | \(1.8\cdot10^8\) | 921 | | \(1.9\cdot10^8\) | 941 | | \(2\cdot10^8\) | 960 | Thus there are **241 certified values in \([10^8,2\cdot10^8)\)** beyond the range of the current OEIS b-file. The first 20 are and the final 20 below \(2\cdot10^8\) are For example, direct independent scans give (d) Among the 960 values: | prime-exponent pattern | count | |---|---:| | \(1+1\) | 922 | | \(1+1+1\) | 23 | | \(1+1+1+1\) | 6 | | \(1+1+1+1+1\) | 1 | | \(2\) | 7 | | \(2+1\) | 1 | Exactly eight are nonsquarefree: All 960 have exactly one witness \(n\). This last observation is finite data only; it is not asserted uniformly. The five-prime example is Indeed, a separate multiplication/primality check verified (d) The final run performed all of the following: \(10^6\), where both methods returned the same 131 integers and witnesses; value \(99\,795\,337\). Canonical lines Run: The default run uses only the Python standard library. On this VM it used 68.52 seconds wall time and 77,920 KiB maximum RSS. Internally it checked \(n\leq14141\), sieved 993,933 primes through 15,384,615, processed 3,218 relevant \(n\), and made 9,980 block gcds. For a prime \(p\), define if and only if Prime squares require the stronger lift modulo \(p^2\), and products with three or more prime factors require a common witness for every prime-power factor. (d) The finite data show why (7) is the main numerical obstruction: 922 of the first 960 values are squarefree semiprimes. (c) A random-residue model predicts that these cross-prime coincidences are very sparse, but that model supplies no uniform error term and is not used as proof. The exact missing analytic lemma is already visible in the restricted semiprime question: estimate of this strength. Bounds for how many distinct residues the factorial sequence occupies modulo one prime do not control the specified residue \(-1\) simultaneously modulo \(p\) and \(q\). Even proving (8) would still leave uniform treatment of prime powers and common intersections of three or more prime-power witness sets. (d) Computation cost wall. Extending the same exact Python computation to \(10^9\) would require \(n<31\,623\) and primes through at least \(58\,823\,529\) (already forced by \(n=16,p=17\)). Extrapolating the measured \(10^8\) and \(2\cdot10^8\) runs gives roughly 5–15 CPU-minutes (0.08–0.25 core-hours) and about 0.1–0.3 GB RAM. I did not run it because it would exceed the requested few-minute budget, and a longer finite table would not supply the uniform correlation estimate (8). PARTIAL: Proved the elementary bound \(A(x)\leq(1+o(1))x/\log\log x\) and exactly certified \(A(200000000)=960\), including 241 values beyond the OEIS \(10^8\) table; the \(x^{o(1)}\) claim remains open at the cross-prime factorial-correlation step.common = gcd(factorial + 1, block_product)
for q in primes_in_block:
if common % q == 0:
relevant_primes.append(q)
# Recover v_q(n!+1), then form every product below X.
for q in relevant_primes:
while residual % q == 0:
residual //= q
exponent[q] += 1
3. A global density-zero bound
Theorem
Proof
A matching-scale elementary construction only at the logarithmic end
4. Exact computation through \(2\cdot10^8\)
Certified count table
100227431 100347833 100413697 100839833 100966727
101150461 101671667 101700509 101920531 101960623
102182161 102190469 102607441 102703933 103430519
103480999 103580573 104505013 104729117 104771231
189172153 190002377 190341313 190397173 190460383
191151277 192423271 192734741 194490823 194570603
195611149 196309783 196779521 197160037 197535997
198660673 198674293 199595467 199886243 199899121
Structural finite data
Independent checks and reproducibility
u:n1,n2,... for the 960-value certificate have SHA-2565d32210f884e15884d55629db48eaf11bfded8a5ce88b41fd0e872a695f7a1bf
python runs/erdos1073_wave8c_reverify.py
5. What remains, precisely