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:

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

2. [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.

3. [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:

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

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

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

4. 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*](https://arxiv.org/abs/2006.06197). 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 }mThe 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