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

Erdős problem 1072 — wave 8c

Access/research date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous-modulo-named-theorem: the deduction is proved here, but uses the explicitly named published result.
(c) plausible/structural-unverified: heuristic only.
(d) computational-only: exhaustive only in the stated finite range.

0. Mandatory live-page audit

I fetched the rendered live page and its discussion thread through the Bright Data browser path, not datacenter curl.

The live page at <https://www.erdosproblems.com/1072> showed:

status OPEN;
0 claimed proofs;
Currently working on this problem: None;
Interested in collaborating: None;
all the other participation markers (“likes”, “looks difficult”, “looks

tractable”, “results could be formalisable”, and “working on formalising”) as None;

one comment, by Sayan Dutta at 17:06 on 30 January 2026;
last problem-page edit: 4 October 2025;
linked OEIS entries A073944, A072937, and A154554;
linked formalisation: “Yes”.

Thus no stop condition was present.

Verbatim current statement

For any prime $p$, let $f(p)$ be the least integer such that $f(p)!+1 \equiv 0\pmod p$.
Is it true that there are infinitely many $p$ for which $f(p)=p-1$? Is it true that $f(p)/p\to0$ for almost all $p$?

The page says that Erdős, Hardy, and Subbarao believed that the number of $p\le x$ with $f(p)=p-1$ is $o(x/\log x)$, and that the questions occur in problem A2 of Guy's collection.

The sole comment makes two points:

Wilson's theorem gives

\[ f(p)=p-a\quad\Longrightarrow\quad p\mid (a-1)!+(-1)^a. \] Hence no fixed $a>1$ can occur for infinitely many $p$.

It links Li Lai's paper on the largest prime divisor of $n!+1$, describing

its consequence as $f(p)/p\le0.138$ infinitely often.

There is a harmless one-prime convention discrepancy in the page's external data. A073944 starts its search at $n=1$, so $f(2)=1$. The linked Lean file defines an infimum over all natural $n$, so $0!=1$ gives $f(2)=0$. Everything below concerning odd primes or asymptotics is independent of this. The finite table uses the A073944/least-positive convention.

1. Primary-source audit

The following source claims were checked against the actual papers, not against secondary summaries.

(b) 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. Problem G on page 557 defines this $f(p)$, asks both live-page questions, records the $o(x/\log x)$ belief for the maximal primes, and says that Erdős believed $f(p)/p\to0$ for almost all $p$.

(b) Richard K. Guy, Unsolved Problems in Number Theory, third edition,

Springer (2004), DOI 10.1007/978-0-387-26677-0. Its A2 section is “Primes connected with factorials”. I use no uninspected theorem from the book.

(b) Li Lai, “On the largest prime divisor of $n!+1$”,

arXiv:2103.14894, now Bulletin of the Australian Mathematical Society 113 (2026), 390–403, DOI 10.1017/S0004972725100543. Theorem 1.1 proves, with $P(m)$ the largest prime divisor, \[ \limsup_{n\to\infty}\frac{P(n!+1)}n \ge C:=1+9\log2=7.238324625039508\ldots \] and, more strongly, for every $\epsilon>0$, the set of $n$ with $P(n!+1)>(C-\epsilon)n$ has positive lower asymptotic density. Lemma 2.2 gives the uniform interval multiplicity bound \[ \#\{n\in J:p\mid n!+1\}\le C_0|J|^{2/3} \tag{1} \] for a prime $p$ and an interval $J\subset[1,p)$.

(b) O. Klurman and M. Munsch, “Distribution of factorials modulo $p$”,

Journal de Théorie des Nombres de Bordeaux 29 (2017), 169–177, DOI 10.5802/jtnb.974. This gives average information about the number of residue classes missed by the full factorial sequence. It does not force the particular residue $-1$, much less force it in an initial interval $n=o(p)$.

The literal decimal in the live comment needs care. The reciprocal of Lai's constant is

\frac1C=0.138153516428471\ldots,

not a number at most $0.138$. The rigorous consequence is:

for every $c>1/C$, infinitely many distinct primes satisfy $f(p)/p<c$;
in particular, $f(p)/p<0.1382$ infinitely often.

Thus “0.138” is valid only as a three-decimal rounded description, not as the literal inequality $f(p)/p\le0.138$.

Targeted searches using the exact definition, both question wordings, the Hardy–Subbarao title/DOI, and forward searches around factorial residue distribution found no primary source claiming either question solved. The only direct quantitative improvement located was Lai's result above. This is an honest search report, not a proof that no uncatalogued paper exists.

The verifier downloads the three primary PDFs used above and checks their exact SHA-256 hashes:

Hardy--Subbarao 2002  4fc0f7ff620e23239d530c29edac12b5943fb9f5f9021907c2ad082a358c1c8e
Lai 2026              86448266ec4761456c0758a33243b63aec5c41a121fbc09afcc1de7b57e6a1f6
Klurman--Munsch 2017  f664bc0b4939d48016292aad5c56c7d0b00f46c638edb08df7d7b2ec6ac5b796

2. Exact Wilson-reflection formula

Lemma

(a) Let $p$ be an odd prime and $0\le k\le p-2$. Then

(p-1-k)!\equiv-1\pmod p \quad\Longleftrightarrow\quad k!\equiv(-1)^k\pmod p. \tag{2}

Proof. Put $n=p-1-k$. The last $k$ factors in $(p-1)!$ are

(n+1)(n+2)\cdots(p-1) \equiv(-k)(-(k-1))\cdots(-1)=(-1)^k k!\pmod p.

Wilson's theorem therefore gives

n!\,(-1)^k k!\equiv-1\pmod p.

Since all factors are nonzero modulo $p$, $n!\equiv-1$ is equivalent to $(-1)^k k!\equiv1$, which is (2). $\square$

Define

K(p):=\max\{0\le k\le p-2:k!\equiv(-1)^k\pmod p\}.

The set is nonempty because $k=0$ works. Formula (2) gives the exact identity

\boxed{f(p)=p-1-K(p).} \tag{3}

Consequently:

(a) $f(p)=p-1$ if and only if

\[ k!\not\equiv(-1)^k\pmod p\qquad(1\le k\le p-2). \tag{4} \] This is the independent criterion used by the second verification kernel.

(a) If $f(p)=p-a$, then $K(p)=a-1$, and hence

\[ p\mid (a-1)!-(-1)^{a-1}=(a-1)!+(-1)^a. \tag{5} \] This recovers the live comment and makes its maximality condition exact.

A uniform endpoint gap

The fixed-$a$ observation can be made uniform. Let

L(p):=\max\{A\ge2:(A-1)!+1<p\}.

(a) For every sufficiently large prime $p$, either

f(p)=p-1 \quad\text{or}\quad f(p)\le p-L(p)-1. \tag{6}

Indeed, if $f(p)=p-a$ with $2\le a\le L(p)$, then the positive integer in (5) is at most $(a-1)!+1<p$, so it cannot be divisible by $p$. Thus a nonmaximal value has $a\ge L(p)+1$. Since

(L(p)-1)!+1<p\le L(p)!+1,

Stirling's formula gives

L(p)\sim\frac{\log p}{\log\log p}.

Therefore the endpoint $p-1$ is asymptotically isolated:

\boxed{f(p)=p-1\quad\text{or}\quad p-f(p)\ge(1+o(1))\frac{\log p}{\log\log p}.} \tag{7}

This does not prove that the maximal alternative occurs infinitely often, but it rules out an entire growing window immediately below it.

3. An exact reduction of the “almost all” question

For $\eta>0$, define

M_\eta(X):=\prod_{1\le n\le\lfloor\eta X\rfloor}(n!+1).

(a) The second question is equivalent to the following prime-coverage statement, for every fixed $\eta>0$:

\#\{p\in(X,2X]:p\nmid M_\eta(X)\} =o\!\left(\frac X{\log X}\right). \tag{8}

To see one direction, if $p\mid M_\eta(X)$ and $p>X$, then some $n\le\eta X$ has $p\mid n!+1$, so $f(p)/p<\eta$. Conversely, if $p\in(X,2X]$ and $f(p)/p\le\eta$, then $f(p)\le2\eta X$, so $p\mid M_{2\eta}(X)$. Since the assertion ranges over every positive $\eta$, the harmless factor 2 proves equivalence.

Equation (8) is the precise missing lemma. It asks for a lower bound on the coverage of a fixed dyadic interval of primes by the prime divisors of many shifted factorials. Largest-prime-factor theorems select some large divisor of each $n!+1$, while factorial value-set theorems count residues for one fixed prime. Neither supplies (8).

4. A quantitative corollary of Lai's theorem

The page comment records only “infinitely often”. Combining both parts of Lai's theorem gives a quantitative counting result.

Corollary

(b) Let $C=1+9\log2$. For every $c>1/C$, there is a constant $\kappa_c>0$ such that, for all sufficiently large $Y$,

\boxed{ \#\left\{p\le Y:\frac{f(p)}p<c\right\} \ge \kappa_c\left(\frac{\log Y}{\log\log Y}\right)^{1/3}.} \tag{9}

Proof. Choose $\lambda<C$ with $1/\lambda<c$. Lai's Theorem 1.1 provides a constant $\delta_\lambda>0$ such that, for every sufficiently large $x$, at least $\delta_\lambda x$ integers $n\le x$ satisfy

q_n:=P(n!+1)>\lambda n.

For each such $n$,

f(q_n)\le n,\qquad \frac{f(q_n)}{q_n}<\frac1\lambda<c. \tag{10}

A fixed prime $q$ can be equal to $q_n$ only when $q\mid n!+1$. Apply Lai's Lemma 2.2 to the portion of $[1,x]$ lying below $q$. Equation (1) shows that one $q$ accounts for at most $C_0x^{2/3}$ of the witnesses. Hence at least

\frac{\delta_\lambda}{C_0}x^{1/3}

distinct good primes occur. Every one is at most $n!+1\le x!+1$. Taking $x$ maximal with $x!+1\le Y$ and using $x\sim\log Y/\log\log Y$ proves (9). $\square$

This is far below positive density among primes: (9) is polylogarithmic in $Y$, whereas the desired conclusion concerns $\sim Y/\log Y$ primes. It is nevertheless a genuine unconditional quantitative strengthening of the bare infinitude consequence.

5. Exhaustive computation through $500{,}000$

Independent algorithms

(d) The standalone checker computes every prime $p\le500000$ and every exact $f(p)$ in two ways:

a direct forward scan of $n!\pmod p$, using the machine's native remainder

operation and stopping at the first $-1$;

a full scan of $k!\pmod p$ using (3), with an independently implemented

fixed-modulus Barrett reduction.

The two answers are asserted equal for every prime. A third plain-Python implementation recomputes all primes through 5000; a separate Python sieve checks the completeness of the C++ prime list.

The mathematical core is:

def direct_f(p):
    fact = 1
    for n in range(1, p):
        fact = fact * n % p
        if fact == p - 1:
            return n

def reflected_f(p):
    fact, best = 1, p - 1
    for k in range(1, p - 1):
        fact = fact * k % p
        if fact == (p - 1 if k & 1 else 1):
            best = min(best, p - 1 - k)
    return best

The complete checker, including the faster kernel, frozen expected values, source-file hashes, endpoint-gap checks, and OEIS comparisons, is erdos1072_wave8c_verify.py.

Run:

python3 runs/erdos1072_wave8c_verify.py --check-sources

To reconstruct all 41,538 rows:

python3 runs/erdos1072_wave8c_verify.py \
  --dump-table /tmp/erdos1072_pairs.csv

The ASCII format is one p,f pair per line. Its SHA-256 is

56ea5fb0678879fccd6037abb2061b984bd12bf42bc8ff82dc8d7347cc6bc6e2

The final run used 34.66 seconds wall time, 118.52 CPU-seconds, and 85,916 KB maximum resident memory. It ended with VERIFIED.

Exact aggregate table

All inequalities in this table were evaluated by integer cross-multiplication. The single prime $2$ uses the least-positive/A073944 convention.

$X$	$\pi(X)$	$f=p-1$	$f\le p/8$	$f\le p/4$	$f\le p/2$	$f\le3p/4$
100	25	12 (48.000%)	1 (4.000%)	3 (12.000%)	12 (48.000%)	15 (60.000%)
1,000	168	65 (38.690%)	14 (8.333%)	29 (17.262%)	84 (50.000%)	98 (58.333%)
10,000	1,229	467 (37.998%)	132 (10.740%)	251 (20.423%)	644 (52.400%)	708 (57.608%)
100,000	9,592	3,433 (35.790%)	1,106 (11.530%)	2,071 (21.591%)	5,224 (54.462%)	5,727 (59.706%)
200,000	17,984	6,413 (35.659%)	2,087 (11.605%)	3,920 (21.797%)	9,774 (54.348%)	10,742 (59.731%)
500,000	41,538	14,774 (35.567%)	4,893 (11.780%)	9,202 (22.153%)	22,639 (54.502%)	24,842 (59.806%)

At the final cutoff, exactly 5,380 primes (12.952%) satisfy $f(p)/p<0.1382$, while 5,375 satisfy the literal $f(p)/p\le0.138$. These finite counts do not imply either asymptotic claim.

The full computation agrees with all 10,000 published terms of A073944 (ending at the 10,000th prime, 104729) and all 1,000 published terms of A154554. Thus the dual computation extends the checked $f(p)$ table from prime 104729 to prime 499979.

A transparent small certificate

(d) The strict record-low ratio in the range is

p=329891,\qquad f(p)=10,\qquad \frac{f(p)}p=\frac{10}{329891}.

The sieve verifies that $329891$ is prime, and

10!+1=3628801=11\cdot329891.

For $1\le n\le8$, $n!\le40320<329890$, and

9!=362880\equiv32989\not\equiv-1\pmod{329891}.

Thus the minimality check is visible without trusting a long residue list.

The last five maximal primes below the cutoff are

499943,\ 499957,\ 499969,\ 499973,\ 499979,

each with $f(p)=p-1$, computationally only.

6. What remains and why current machinery stalls

First question

Formula (4) reduces the question exactly to proving that infinitely many primes avoid every signed congruence

k!\equiv(-1)^k\pmod p,\qquad1\le k\le p-2.

The range and the modulus grow together. Fixed-polynomial Chebotarev arguments do not apply, and value-set cardinality lower bounds do not control avoidance of these two parity-dependent target residues. The 14,774 finite examples and their apparent 35.6% frequency are (d) only; no uniformity step follows.

Second question

The exact missing statement is (8). Known factorial value-set bounds cannot distinguish $-1$ from a missed residue, while large-prime-factor results can choose only $ \gg(\log Y/\log\log Y)^{1/3}$ distinct good primes by the argument above. Bridging the gap to $Y/\log Y$ would require a new fixed-target prime-coverage theorem for $\prod_{n\le\eta X}(n!+1)$, not a larger finite scan.

The present dual scan costs $\Theta(\sum_{p\le X}p)=\Theta(X^2/\log X)$ modular steps. Extrapolating the measured run gives about 10.7 core-hours for $X=10^7$, or roughly $\$0.54$–$\$1.07$ at $\$0.05$–$\$0.10$ per core-hour (about 2.7 hours wall time on four comparable cores). That computation was not run: it would add data but would not supply either missing uniformity argument.

PARTIAL: proved an exact Wilson-reflection reduction and growing endpoint gap, derived a quantitative $(\log Y/\log\log Y)^{1/3}$ lower bound for every cutoff $c>1/(1+9\log2)$, and independently verified every $f(p)$ for $p\le500000$; both original questions remain open.

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