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:

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

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

nonmaximal value has $a\ge L(p)+1$. Since

\[ (L(p)-1)!+1Stirling'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)}pProof. Choose \(\lambda

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\lambdaA 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:

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

operation and stopping at the first $-1$;

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