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<x\) such that \(n!+1\equiv 0\pmod{u}\) for some \(n\). Is it true that \(A(x)\leq x^{o(1)}\)?

Source: live page and LaTeX view.

(d) Page status. The page says OPEN. It displayed:

• 0 comments;
• 0 claimed proofs;
• “Currently working on this problem: None”;
• “Interested in collaborating: None”;
• last edited 06 October 2025.

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. Source and literature audit

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)\).

1. (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.

1. (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.

1. (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.

1. (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.

2. Elementary exact reductions

Write \(P^-(u)\) for the least prime divisor of \(u>1\).

Lemma 1

(a) If \(u\mid n!+1\), then every prime divisor of \(u\) is greater than \(n\). In particular,

Proof. If a prime \(p\mid u\) had \(p\leq n\), then \(p\mid n!\) and \(p\mid n!+1\), which is impossible. \(\square\)

Lemma 2: finite search identity

(a) If \(u<X\) is composite and \(u\mid n!+1\), then

Consequently, with \(s=\lfloor\sqrt{X-1}\rfloor\),

This identity is exact, not heuristic. The apparently unbounded witness search therefore terminates at \(n=s-1\).

Lemma 3: how to enumerate without factoring a huge factorial

Fix \(n<s\), put \(N=n!+1\), and let \(p\) be the least prime at most \(s\) 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<X\) of \(N\) obeys

Proof. A composite \(d<X\) has a least prime factor \(r\leq s\), so \(p\leq r\). 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<X\). The verifier splits the primorial into blocks of at most 4096 primes so it never has to factor \(N\) or hold one enormous global primorial.

Core executable logic:

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

The full standard-library-only implementation is erdos1073_wave8c_reverify.py.

3. A global density-zero bound

This does not reach the requested subpolynomial bound, but it is a rigorous uniform estimate.

Theorem

(a) As \(x\to\infty\),

In particular, \(A(x)=o(x)\).

Proof

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<x\) is counted, witnessed by \(n\). If \(n<y\), then

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

No sieve theorem is hidden here: the error is at most one for each of the \(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 matching-scale elementary construction only at the logarithmic end

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

4. Exact computation through \(2\cdot10^8\)

All counts here use the problem's strict convention \(u<X\).

Certified count table

(d) The complete enumeration gives:

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

100227431 100347833 100413697 100839833 100966727
101150461 101671667 101700509 101920531 101960623
102182161 102190469 102607441 102703933 103430519
103480999 103580573 104505013 104729117 104771231

and the final 20 below \(2\cdot10^8\) are

189172153 190002377 190341313 190397173 190460383
191151277 192423271 192734741 194490823 194570603
195611149 196309783 196779521 197160037 197535997
198660673 198674293 199595467 199886243 199899121

For example, direct independent scans give

Structural finite data

(d) Among the 960 values:

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

Independent checks and reproducibility

(d) The final run performed all of the following:

• reconstructed every candidate using (1)–(2);
• factored every output integer independently by trial division;
• recomputed \(n!\bmod u\) from 1 for all 960 displayed witness pairs;
• ran a completely different literal modulus-by-modulus scan through

\(10^6\), where both methods returned the same 131 integers and witnesses;

• independently matched all 719 OEIS values below \(10^8\), including its last

value \(99\,795\,337\).

Canonical lines u:n1,n2,... for the 960-value certificate have SHA-256

5d32210f884e15884d55629db48eaf11bfded8a5ce88b41fd0e872a695f7a1bf

Run:

python runs/erdos1073_wave8c_reverify.py

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.

5. What remains, precisely

For a prime \(p\), define

(a) For distinct primes \(p<q\), the squarefree semiprime \(pq\) is counted 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:

The full conjecture would imply (8), yet the literature located above gives no 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.