Count composite $u$ with $n!+1\equiv0\pmod u$ for some $n$: is $A(x)\leq x^{o(1)}$? (Erdős #1073)
Statement
For $x\geq 1$ let $A(x)$ be the number of composite integers $u<x$ for which there exists some $n$ with $n!+1\equiv 0\pmod{u}$ (equivalently, $u$ divides $n!+1$ for some $n$). By Wilson's theorem every prime $u$ has this property (with $n=u-1$), so the interest is in composite $u$. Is it true that $$A(x)\leq x^{o(1)}?$$ That is, are such composite $u$ extremely sparse?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else a full written proof) that $A(x)\le x^{o(1)}$ (with an explicit slowly-growing exponent bound), OR a disproof showing $A(x)\ge x^{c}$ for some fixed $c>0$ (e.g. by exhibiting a certified infinite family of composite solutions of positive exponent density). ADVANCES, each independently checkable: any proven non-trivial upper bound on $A(x)$ — for instance $A(x)\ll x^{1-c}$ or $A(x)\le x/(\log x)^{C}$ — improving on the trivial $A(x)\le x$, with proof; OR a reproducible extension of the sequence A256519 of composite solutions to a new range, delivered with the membership-testing program and an empirical growth estimate for $A(x)$ (state the previous range in words). Deliver the proof or the search code plus the certified new terms and bound.
Background
A question of Erdős raised in discussions with Hardy and Subbarao [HaSu02], mentioned in problem A2 of Guy's Unsolved Problems in Number Theory; listed as open on erdosproblems.com/1073 (fetched 2026-07-21, status 'open'). Wilson's theorem gives $u\mid(u-1)!+1$ exactly when $u$ is prime, so the objects here are composite $u$ dividing some $n!+1$; the sequence of such $u$ begins $25,121,169,437,\ldots$ (OEIS A256519). The conjecture $A(x)\le x^{o(1)}$ asserts these composites are sub-polynomially rare up to $x$; nothing better is proven and no asymptotic is known. A Lean-formalised statement is available in the formal-conjectures project. The problem sits in the same factorial-congruence circle as Erdős #1072 and #1074 (erdosproblems.com/1072, erdosproblems.com/1074). Attacker's tool: for each composite $u$ test membership by iterating $n!\bmod u$ for $n<u$ (a finite check, since the residues either reach $0$ or become $\equiv-1$ within one period), extend A256519 well beyond its current range and fit the empirical growth of $A(x)$; complement with analytic bounds on how often $-1$ is a factorial value modulo composite $u$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1073 (T. F. Bloom) | website |
| REF-02 | OEIS A256519 — composite u dividing n!+1 for some n | website |
| REF-03 | Lean formalisation of Erdős #1073 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.