Skip to content

Erdős Problem #419

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number theory, factorials.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Let \(\tau(n)\) count the positive divisors of \(n\). A factorial \(n!\) is the product \(1\cdot2\cdots n\), and it gains new prime factors and higher prime powers as \(n\) increases. Erdős Problem 419 studies how quickly the number of divisors of factorials changes from one step to the next. Its central sequence is

\[ R(n)=\frac{\tau((n+1)!)}{\tau(n!)}. \]

The question asks for the limit points of this sequence: the real numbers approached by \(R(n)\) along some subsequence with \(n\) tending to infinity. It is not the same as asking for a single ordinary limit. In particular, some subsequences may behave differently from others without contradicting the existence of an exact, countable set of limit points.

The problem was posed in Erdős and Graham's 1980 book. The final answer is unusually explicit:

\[ \{1\}\ \cup\ \left\{1+\frac1k:k=1,2,3,\ldots\right\}. \]

This set is bounded between \(1\) and \(2\), contains \(2\) and \(3/2\), and has \(1\) as its sole accumulation point. The mathematical obligation is to show both that no other limit points occur and that every number displayed really occurs as a subsequential limit.

A small example

Divisor counts can be computed exactly from the prime factorization. If \(n=p_1^{a_1}\cdots p_r^{a_r}\), each divisor chooses an exponent between \(0\) and \(a_i\) independently, so

\[ \tau(n)=\prod_{i=1}^{r}(a_i+1). \]

For \(n=5\), we have \(5!=120=2^3\cdot3\cdot5\), so \(\tau(5!)=4\cdot2\cdot2=16\). Meanwhile \(6!=720=2^4\cdot3^2\cdot5\), giving \(\tau(6!)=5\cdot3\cdot2=30\). Therefore

\[ R(5)=\frac{30}{16}=\frac{15}{8}. \]

For \(n=6\), the new factor \(7\) is prime and \(7!=6!\cdot7\). It doubles the number of divisors without affecting previous prime exponents, so

\[ R(6)=\frac{60}{30}=2. \]

The exact arithmetic was independently checked using integer prime factorization and also yields \(\tau(8!)=96\), so \(R(7)=96/60=8/5\). Neither \(15/8\) nor \(8/5\) needs to be a limit point. A term of the sequence can lie outside its eventual limit-point set; the definition concerns infinitely far-out indices.

There is an important immediate source of the limit point \(2\): whenever \(n+1=p\) is prime, the new factor \(p\) did not divide \(n!\), and hence \(R(n)=2\). Since there are infinitely many primes, \(2\) occurs infinitely often. This is a genuine proof of one limit point, not merely a finite example.

What is known

Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 83, already noted the limit points \(1+1/k\) and \(1\), but asked whether others could occur. The historical source is available in the monograph scan.

The complete characterization appeared in P. Erdős, S. W. Graham, A. Ivić and C. Pomerance, On the number of divisors of \(n!\), in Analytic Number Theory, Progress in Mathematics 138 (1996), pp. 337–355; publisher DOI. Corollary 1 gives precisely the set displayed above. The maintained Erdős Problems #419 page reproduces a concise argument communicated by Mehtaab Sawhney and notes the earlier 1996 result. It currently labels the problem solved.

Here is the mechanism. Writing \(v_p(m)\) for the exponent of prime \(p\) in \(m\), the exact formula

\[ R(n)=\prod_{p\mid n+1} \left(1+\frac{v_p(n+1)}{v_p(n!)+1}\right) \]

follows immediately from \(\tau\). For primes \(p\leq n^{2/3}\), the contribution becomes negligible in aggregate as \(n\) grows, because \(v_p(n!)\) is large relative to \(v_p(n+1)\). There can be at most one prime divisor \(p>n^{2/3}\) of \(n+1\) for large \(n\). If one exists, write \(n+1=kp\). Then \(p\) appears exactly once in \(n+1\), and \(v_p(n!)=k-1\) for sufficiently large \(p\). Its contribution is \(1+1/k\). This is why the only possible limiting shapes are \(1\) and \(1+1/k\).

To realize \(1+1/k\) for fixed \(k\), choose primes \(p\) tending to infinity and take \(n=kp-1\). The large-prime factor contributes \(1+1/k\) while the remaining finite collection of small prime factors contributes a factor tending to \(1\). To realize \(1\), choose \(n+1\) as a power of \(2\), for which the ratio approaches \(1\). These statements explain the published characterization but are not presented as a newly certified replacement for the complete 1996 proof.

GCL's current state

The original issue #1689 pins teorth catalogue commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen entry says solved and reports Lean proof status. The maintained page also reports SOLVED (LEAN), although this is a status description rather than a session-specific build result.

The pinned FormalConjectures 419.lean, blob e865969b20ec9e0944515bf01e86a290125042bb, defines a real-valued factorial divisor ratio and the candidate set \(\{1\}\cup\{1+1/k:k\geq1\}\) using real cluster points along indices tending to infinity. Its theorem links an external Lean proof, but the pinned theorem body is still by sorry. A link to another repository does not establish that this article has replayed its trust chain. No such replay was performed.

The authenticated source return on original issue #1689 is authenticated original RESULT/1. This article does not change the V2 accepted-admissions ledger or assert mathematical novelty.

What remains

The original limit-point question is solved at published-paper level. The bounded next task is to produce a rigorous, readable source concordance between the 1996 Corollary 1, Sawhney's concise proof, and the pinned formal statement. In particular, verify the \(n\) versus \(n+1\) index shift, the real cluster-point definition, and whether all sequences under discussion have strictly positive denominator.

A useful small fixture is to factor \(n!\) exactly for \(3\leq n\leq12\), calculate \(R(n)\) as rational numbers, and compare directly with the valuation-product identity. Acceptance requires exact agreement of both calculations and a source-level mapping from the printed 1996 corollary to the formal limit-point set. Falsification includes a wrong exponent valuation, replacing finite terms by limiting values, or inferring proof verification from the pinned sorry. Stop after the mathematical concordance and arithmetic check, leaving any formal replay as a separately governed task.

Sources and claim boundaries

Original question: Erdős–Graham (1980), printed p.83. Primary resolving paper: Erdős, Graham, Ivić and Pomerance (1996), especially Corollary 1. Maintained argument and status: Problem #419, accessed 2026-10-13. Frozen GCL issue: #1689. Formal source: pinned 419.lean.

Exact integer and rational sample calculations are independently checked. The infinite-limit theorem is credited to the published primary paper, and the external Lean claim has not been replayed here. No novel mathematical result, proof certification, or editorial admission is asserted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1689 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction