Erdoes #1074 - working report - Erdős Problem a Day

Erdős problem #1074 — live-page audit, exact computations, and the remaining walls

Date: 2026-07-28 (UTC)

Outcome

The problem is still open. I obtained three independently checkable partial results:

[a] A Wilson-reflection lemma reduces the Pillai-prime test to only the

first half of the factorial orbit modulo $p$, with an exact description of the fixed residues that must be hit.

[d] Two different exhaustive kernels agree on every prime

$p\le 500000$: there are exactly $21969$ Pillai primes among the $41538$ primes in that interval, a ratio of $0.5288892098801098$. This reproduces all 10000 published OEIS terms through $213043$ and supplies 11969 further classifications.

[d] Explicit factor/primality certificates classify $S$ exactly

through $139$: $|S\cap[1,100]|=82$ and $|S\cap[1,139]|=120$. Every $141\le m\le153$ is in $S$, while $154\notin S$ because $154!+1$ is prime. The sole intervening unknown is $m=140$, for which $140!+1$ is a proven composite of 242 digits but no factor was found in the checked public data.

None of these finite facts proves either density exists.

0. Mandatory live-page check

I fetched the rendered page and its discussion thread through the Bright Data browser path, rather than direct curl.

Live status on 2026-07-28:

OPEN
0 claimed proofs for this problem
Currently working on this problem: None
Interested in collaborating: None
five comments; none is a proof claim or a current-worker marker
page last edited 04 October 2025

Thus the required stop condition was not triggered.

Current statement (verbatim wording; mathematical typography normalized)

Let $S$ be the set of all $m\geq 1$ such that there exists a prime $p\not\equiv 1\pmod m$ such that $m!+1\equiv0\pmod p$. Does \[ > \lim \frac{|S\cap[1,x]|}{x} > \] exist? What is it?
Similarly, if $P$ is the set of all primes $p$ such that there exists an $m$ with $p\not\equiv1\pmod m$ such that $m!+1\equiv0\pmod p$, then does \[ > \lim \frac{|P\cap[1,x]|}{\pi(x)} > \] exist? What is it?

Source: Erdős Problems #1074, accessed 2026-07-28.

Results and comments actually present on the live page

[b, Hardy--Subbarao Theorems 2.1 and 2.12] Both $S$ (the EHS

numbers) and $P$ (the Pillai primes) are infinite.

[a] Chowla's examples are

$23\mid14!+1$ and $23\mid18!+1$.

[d, historical computation] The page reports Hardy and Subbarao's old

computation to $2^{10}$, their then-observed ratios near $1/2$, and their belief (shared later by Erdős) that the density of $S$ is $1$. The exact historical finite ratios are not reliable as current data; explicit counter-witnesses to that old count are given below.

[c] The March 2026 comment by Zeraoulia Rafik proposes the density-one

heuristic that all prime factors of $m!+1$ landing in the single class $1\bmod m$ should be extremely unlikely.

[c] Thomas Bloom agrees with the density-one guess and notes that it

matches the eventual Hardy--Subbarao--Erdős belief.

Two October 2025 comments concern a typo and a joke about that typo.
[a] Dogmachine observes that density one for $S$ implies that

$n!+1$ is composite for almost all indices $n$. Indeed, if $n!+1$ is prime, then its only prime factor is $n!+1\equiv1\pmod n$, so $n\notin S$.

The site itself warns that comments are unverified.

1. Literature search

I searched exact phrases "EHS numbers", "Pillai primes", the defining factorial congruence, the title of the original paper, arXiv, journal indexes, and the citation graph of the 2002 article. I found no post-2002 primary source claiming either density.

The primary sources I actually opened and hash-checked were:

P. Erdős and C. L. Stewart,

On the greatest and least prime factors of $n!+1$, Journal of the London Mathematical Society (2) 13 (1976), 513--519. [b] Their Theorem 1 gives $p(n!+1)>n+(1-o(1))\log n/\log\log n$ when $n+1$ is composite, and $p(n!+1)>n+\epsilon(n)n^{1/2}$ for almost all $n$, for every positive $\epsilon(n)\to0$. These lower bounds are compatible with every factor being $1\bmod n$, so they do not decide membership in $S$. The paper explicitly presents “$n!+1$ is composite for almost all $n$” as a guess, not a theorem. SHA-256: fe38ce84006e7f7627bf4ff087c93d0ed7f2dadaf0848ec766d2ec85fd62a697.

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. [b] Theorems 2.1 and 2.12 prove infinitude; Problems A and B ask the two density questions. SHA-256 of the checked PDF: 4fc0f7ff620e23239d530c29edac12b5943fb9f5f9021907c2ad082a358c1c8e.

Li Lai,

On the largest prime divisor of $n!+1$, Bulletin of the Australian Mathematical Society 113 (2026), 390--403, DOI 10.1017/S0004972725100543. [b] Its Theorem 1.1 proves \[ \limsup_{n\to\infty}\frac{P^+(n!+1)}n\ge 1+9\log2 \] and a positive-lower-density version. It explicitly uses the same Wilson reflection $p\mid n!+1\Rightarrow p\mid(p-1-n)!+1$ for odd $n$. It does not control the residue of a prime factor modulo $n$, so it does not answer the first density question. SHA-256: 86448266ec4761456c0758a33243b63aec5c41a121fbc09afcc1de7b57e6a1f6.

Oleksiy Klurman and Marc Munsch,

Distribution of factorials modulo $p$, Journal de Théorie des Nombres de Bordeaux 29 (2017), 169--177, DOI 10.5802/jtnb.974. [b] They prove value-set and average missing-residue results for $n!\bmod p$. These are not lower bounds for hitting the particular residues $1$ or $-1$, which is what #1074 requires. SHA-256: f664bc0b4939d48016292aad5c56c7d0b00f46c638edb08df7d7b2ec6ac5b796.

For a realistic factoring-cost comparison I also checked Boudot--Gaudry-- Guillevic--Heninger--Thomé--Zimmermann, Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment. Their general number field sieve factorization of a balanced 240-digit RSA integer used about $10^3$ core-years. This is a cost analogue, not evidence that $140!+1$ is balanced.

2. Elementary structural reductions

2.1 The complement of $S$

Every prime divisor $p$ of $m!+1$ satisfies $p>m$. Therefore

m\notin S \quad\Longleftrightarrow\quad p\equiv1\pmod m\ \text{for every prime }p\mid m!+1. \tag{2.1}

This is [a]. It also shows precisely why merely proving that $m!+1$ is composite is insufficient: all of its prime factors could still be $1\bmod m$.

The factorial-prime obstruction is immediate:

\{m:m!+1\text{ is prime}\}\subseteq\mathbb N\setminus S. \tag{2.2}

Thus density one for $S$ would imply a zero-density set of factorial-prime indices. Even that weaker statement is not presently known; conversely, zero density of factorial primes would not by itself prove density one for $S$. This is an exact hardness implication, not a heuristic.

2.2 Wilson reflection and a half-interval Pillai test

Let $p$ be odd, $1\le k\le p-2$, and put $M=p-1-k$. Wilson's theorem and reversal of the last $M$ factors give

\begin{aligned} -1 &\equiv(p-1)!\\ &\equiv k!\,(k+1)(k+2)\cdots(p-1)\\ &\equiv k!(-1)^M M! \equiv k!(-1)^kM!\pmod p. \end{aligned}

Hence

M!\equiv\frac{(-1)^{k+1}}{k!}\pmod p. \tag{2.3}

This proves the following [a] exact reconstruction:

if $k$ is odd and $k!\equiv-1\pmod p$, then $M!\equiv-1\pmod p$;
if $k$ is even and $k!\equiv1\pmod p$, then $M!\equiv-1\pmod p$.

When $k<(p-1)/2$, its reflected index $M>(p-1)/2$ cannot be a proper divisor of $p-1$. Consequently either of those two hits immediately makes $p$ a Pillai prime. A third direct possibility is

k\text{ even},\qquad k!\equiv-1\pmod p,\qquad k\nmid p-1.

Scanning $1\le k\le(p-1)/2$, reconstructing $M$, and treating the central point separately is therefore an exact test. Equivalently,

p\notin P \quad\Longleftrightarrow\quad \text{every }m<p\text{ with }m!\equiv-1\pmod p\text{ divides }p-1. \tag{2.4}

The useful sufficient lemma that would settle the second density as $1$ is:

For all but $o(\pi(x))$ primes $p\le x$, some $k<(p-1)/2$ satisfies $k!\equiv(-1)^k\pmod p$, or some even $k<(p-1)/2$ satisfies $k!\equiv-1\pmod p$ with $k\nmid p-1$.

This is currently [c] (unproved). Known factorial value-set results give many distinct values or many missed values, but no lower bound forcing these fixed targets.

3. Exact Pillai-prime computation through $500000$

3.1 Independent algorithms

The standalone verifier contains two C++ kernels and a third Python audit.

Kernel A directly updates fact = fact*m % p for

$1\le m\le p-2$, recording the least admissible $m$.

Kernel B scans only the lower half, uses (2.3), and performs modular

multiplication with Barrett reduction rather than native %.

For every prime the kernels compare the least witness, not just the

yes/no answer.

A simple Python implementation independently repeats the direct definition

for every prime through $5000$.

The essential direct code is:

fact = 1
for m = 1,...,p-2:
    fact = fact*m mod p
    if fact == p-1 and (p-1) mod m != 0:
        return m
return 0

The reflected kernel uses

M = p-1-k
if k is odd  and k! == -1: M! == -1
if k is even and k! == +1: M! == -1

and checks all reconstructed roots against the divisibility condition.

3.2 Verified table

All entries in this subsection are [d] computational-only, albeit exhaustive and dual-verified.

$x$	$\pi(x)$	$\|P\cap[1,x]\|$	ratio
100	25	8	0.3200000000
1,000	168	82	0.4880952381
10,000	1,229	613	0.4987794955
20,000	2,262	1,177	0.5203359859
44,987	4,675	2,478	0.5300534759
100,000	9,592	5,030	0.5243953294
200,000	17,984	9,425	0.5240769573
213,043	19,050	10,000	0.5249343832
250,000	22,044	11,571	0.5249047360
300,000	25,997	13,657	0.5253298458
400,000	33,860	17,830	0.5265800354
500,000	41,538	21,969	0.5288892099

The $x=44987$ row exactly reproduces the last Hardy--Subbarao appendix ratio. The first 10000 computed prime values agree term-for-term with OEIS A063980, whose current b-file ends at $213043$.

The first ten new (prime, least witness) pairs after that endpoint are

(213067,88342) (213091,63426) (213097,49351) (213139,9014)
(213149,49841) (213181,166086) (213193,94509) (213203,33587)
(213209,11960) (213253,2115)

The SHA-256 digest of all 21969 ASCII rows p,least_witness\n is

78c02b39d46898ccd0b703b76e3c005a540d06367effdd6dfdb9126235201f96

The finite ratios fluctuate around $0.52$--$0.53$; they are not evidence for existence of a limit, much less a proof of its value.

The same scan gives rigorous lower bounds for $S$ when only witnesses $p\le500000$ are admitted:

x=500:    at least 277 EHS numbers
x=1000:   at least 516
x=5000:   at least 2083
x=10000:  at least 3666

These are only lower bounds. Their decreasing ratios mainly reflect the fixed prime cutoff and must not be interpreted as density estimates.

4. Exact EHS certificates and the $m=140$ wall

4.1 Exact initial segment

The verifier stores one explicit prime witness for each asserted EHS number and a complete prime factorization (or a primality certificate) for each asserted non-EHS number. It recomputes every factorial and congruence and uses PARI/GP's proven isprime, not a probable-prime flag.

The exact complement through 139 is [d]

\begin{split} [1,139]\setminus S=\{& 1,2,3,4,5,6,7,10,11,12,25,27,28,37,41,46,\\ &73,77,116\}. \end{split} \tag{4.1}

Therefore

|S\cap[1,100]|=82,\qquad |S\cap[1,139]|=120. \tag{4.2}

This corrects the historical $0.55$-level count quoted in the 2002 paper. Two very small omitted examples already show the old list was incomplete:

\begin{aligned} 20!+1 &=20639383\cdot117876683047, &20639383&\equiv3\pmod{20},\\ 21!+1 &=43\cdot439429\cdot2703875815783, &439429&\equiv4\pmod{21}. \end{aligned}

The script checks all 120 witnesses, not just these examples.

It also proves [d]

141,142,\ldots,153\in S,\qquad154\notin S, \tag{4.3}

the last fact following from a rigorous primality certificate for $154!+1$. Thus the next non-EHS integer after 116 is exactly one of

140\quad\text{or}\quad154. \tag{4.4}

4.2 What is known from scratch about $140!+1$

Let $N=140!+1$.

[d] $N$ has 242 decimal digits.
[a, finite modular certificate] $N$ fails the base-2 strong

probable-prime test, which is a conclusive proof that $N$ is composite.

Its decimal SHA-256 identifier is

83b16a213e57afeb46eae9f7a9e2311fc8341b9bfb047a181ecadc184a2e05bd.

[d, external database observation only] The current FactorDB API

returned status C with no proper factor, matching the older public factorial table's notation C242.

One prime divisor $q\not\equiv1\pmod{140}$ would prove $140\in S$. To prove $140\notin S$ by factorization, every prime factor would have to be obtained and certified $1\bmod140$.

I did not launch an unbounded factorization. [c, cost estimate] If $N$ has a 40--60 digit factor, a targeted ECM campaign might cost from hundreds to many thousands of core-hours, depending strongly on the unknown factor size. In the balanced hard case, the closest public benchmark is RSA-240 at about $10^3$ core-years, i.e. roughly $8.8\times10^6$ core-hours on the reference CPUs. Even allowing a substantial modern speedup, this is a $10^6$--$10^7$ core-hour project, not a few-minute calculation. At a representative $\$0.03$--$\$0.06$ per core-hour that is approximately $\$30{,}000$--$\$600{,}000$, with the broad range reflecting both hardware and the unknown factor shape.

5. Why the asymptotic questions remain out of reach

First density

The exact missing input is a residue-sensitive prime-factor theorem:

\#\{m\le x:\ p\equiv1\pmod m \text{ for every }p\mid m!+1\}=o(x). \tag{5.1}

Current theorems forcing a large prime factor of $m!+1$ do not control that factor modulo $m$. Classical small-prime sieving is unusually weak here because every prime divisor of $m!+1$ is already $>m$. Moreover, (2.2) shows that (5.1) contains the still-unproved zero-density factorial-prime statement as a necessary subproblem.

Second density

By (2.3)--(2.4), the exact missing input is an almost-all-primes lower bound for hitting the fixed residues $\pm1$ with the required parity/divisor condition. Existing factorial-residue work supplies upper bounds for the number of solutions or lower bounds for the size of the whole value set; it does not guarantee even one non-Wilson hit of the needed kind for almost all primes.

The computation is quadratic up to logarithms:

\sum_{p\le X}O(p)=O\!\left(\frac{X^2}{\log X}\right).

Extending $500000$ by one or two orders of magnitude would improve the experiment but cannot provide the uniform $o(\pi(x))$ estimate.

6. Reproduction

Full standalone verifier:

erdos1074_wave8c_reverify.py

Run the arithmetic checks:

python runs/erdos1074_wave8c_reverify.py

Also redownload and hash-check the four primary-source PDFs and compare the first 10000 Pillai primes with the current OEIS b-file:

python runs/erdos1074_wave8c_reverify.py --check-sources --check-oeis

On this VM the full dual scan used four threads, about 99 CPU-seconds and 26 seconds wall time. The source/OEIS audit raised total wall time to about 29 seconds. The final output ended VERIFIED.

Claim labels used above:

[a] elementary-rigorous;
[b] rigorous modulo the named published theorem;
[c] plausible/structural-unverified;
[d] computational-only (finite, reproducible, and certificate-checked).

PARTIAL: Exact EHS certificates give 120 members through 139 and isolate 140!+1; two independent scans give 21969 Pillai primes through 500000, but both density limits remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger