Erdős Problem #912

Erdős Problem 912 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/912.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT.
Write the prime factorisation of $n!$ as \[ n! = \prod_{p\le n} p^{k_p(n)} \] where the product is over primes $p$ and $k_p(n)=v_p(n!)\in\mathbb{N}$ is the exponent of $p$ in $n!$. Let \[ h(n):=\big|\{k_p(n): p\le n\text{ prime}\}\big| \] be the number of distinct exponent values appearing in this factorisation. The conjecture asks to prove that there exists a constant $c>0$ such that \[ h(n) \sim c\,\Big(\frac{n}{\log n}\Big)^{1/2}\qquad (n\to\infty), \] where $\log$ is the natural logarithm.

QUICK LITERATURE/CONTEXT CHECK.
The problem text states (without proof here) that Erdős--Selfridge proved the order of magnitude $h(n)\asymp (n/\log n)^{1/2}$. It also reports a heuristic constant $c=\sqrt{2\pi}$. I will not assume any of those results; I will only derive basic identities and provide computational sanity checks.

ATTACK PLAN.
Proof track. Express $k_p(n)$ explicitly (Legendre formula), then analyze how many distinct integers occur among $\{k_p(n)\}$ as $p$ ranges over primes $\le n$.

Reality-check track. Compute $h(n)$ for moderate $n$ and compare to $\sqrt{n/\log n}$.

WORK.
Phase 1: fast reality check (computation). Using Legendre's formula (Lemma 912.1) I computed $h(n)$ exactly for several $n$.

(These values were computed by a direct prime loop and Legendre summation; for example, $h(10^7)=2087$ and $h(3\cdot 10^7)=3503$.)

Lemma 912.1 (Legendre formula). For every prime $p\le n$, \[ k_p(n)=v_p(n!)=\sum_{j\ge 1} \Big\lfloor \frac{n}{p^j}\Big\rfloor. \]

Proof. Among the integers $1,2,\dots,n$, the number divisible by $p$ is $\lfloor n/p\rfloor$, each contributing at least one factor $p$ to the product $n!$. The number divisible by $p^2$ is $\lfloor n/p^2\rfloor$, contributing an additional factor $p$ beyond the first, and so on. Summing the contributions over all powers $p^j$ counts exactly the total exponent of $p$ in $n!$. $\square$

Lemma 912.2 (large primes have single-term exponents). If $p$ is prime and $p>\sqrt{n}$, then \[ k_p(n)=v_p(n!) = \Big\lfloor \frac{n}{p}\Big\rfloor. \]

Proof. By Lemma 912.1, \[ v_p(n!)=\Big\lfloor \frac{n}{p}\Big\rfloor + \Big\lfloor \frac{n}{p^2}\Big\rfloor+\Big\lfloor \frac{n}{p^3}\Big\rfloor+\cdots. \] If $p>\sqrt{n}$ then $p^2>n$, hence $\lfloor n/p^j\rfloor=0$ for every $j\ge 2$. Only the $j=1$ term remains. $\square$

Lemma 912.3 (a crude $O(\sqrt n)$ upper bound on $h(n)$). For every $n\ge 2$, \[ h(n) \le \lfloor \sqrt{n}\rfloor + \pi(\sqrt{n}), \] where $\pi(x)$ is the number of primes $\le x$. In particular $h(n)=O(\sqrt{n})$.

Proof. Split primes into two ranges.

$1$ Primes $p>\sqrt{n}$. By Lemma 912.2, $k_p(n)=\lfloor n/p\rfloor$. As $p$ ranges over $\{\text{primes}:\sqrt{n}<p\le n\}$, the integer $\lfloor n/p\rfloor$ lies in $\{1,2,\dots,\lfloor\sqrt{n}\rfloor\}$. Hence the set of exponents contributed by these primes has size at most $\lfloor\sqrt{n}\rfloor$.

$2$ Primes $p\le \sqrt{n}$. There are exactly $\pi(\sqrt{n})$ such primes, hence they contribute at most $\pi(\sqrt{n})$ distinct exponent values.

Taking the union of the two exponent sets proves the displayed inequality. $\square$

VERIFICATION.

• Lemma 912.1 is the standard valuation counting argument and does not use any unproved prime distribution input.
• Lemma 912.2 correctly uses $p^2>n$ to kill higher terms.
• The computation table is consistent across multiple $n$ and shows $h(n)$ growing roughly like a constant times $\sqrt{n/\log n}$, but does not constitute a proof.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: exact formulae for the exponents $k_p(n)$ (Lemma 912.1) and their simplification for $p>\sqrt{n}$ (Lemma 912.2), plus the crude bound $h(n)\le \lfloor\sqrt n\rfloor+\pi(\sqrt n)$ (Lemma 912.3). Computations up to $n=3\cdot 10^7$ give, e.g., $h(10^7)=2087$ and $h(3\cdot 10^7)=3503$, with ratios $h(n)/\sqrt{n/\log n}$ around $2.65$.

(ii) First gap (crisp): Prove the asymptotic $h(n)\sim c\sqrt{n/\log n}$ for some constant $c>0$, or even prove the existence of the limit $\lim_{n\to\infty} h(n)/\sqrt{n/\log n}$.

(iii) Top 3 next moves:

1. Analyze the map $p\mapsto v_p(n!)$ more sharply: show that for most primes $p$ in a suitable range, $v_p(n!)$ is close to $n/(p-1)$ with controllable error, and convert distinct-value counting into a question about spacing of the values $n/(p-1)$.
2. Reduce to primes in a "main range" $p\asymp \sqrt{n\log n}$ where one expects the spacing between consecutive $v_p(n!)$ to be about $1$; then show that sufficiently many integers are hit as $p$ varies.
3. Use computation to probe the constant: compute $h(n)$ for larger $n$ (say $10^8$ or beyond) and track $h(n)/\sqrt{n/\log n}$ to see whether it drifts toward a stable value.

(iv) Minimal counterexample structure (if the asymptotic were false): a mechanism causing long-range "collisions" $v_p(n!)=v_q(n!)$ for many distinct primes $p\ne q$ in the main range, or conversely large gaps of missing integers among the set $\{v_p(n!):p\le n\}$; such a mechanism would likely be tied to irregular distribution of primes in short intervals.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.
Write the prime factorisation of $n!$ as \[ n! = \prod_{p\le n} p^{k_p(n)} \] where the product is over primes $p$ and $k_p(n)=v_p(n!)\in\mathbb{N}$ is the exponent of $p$ in $n!$. Let \[ h(n):=\big|\{k_p(n): p\le n\text{ prime}\}\big| \] be the number of distinct exponent values appearing in this factorisation. The conjecture asks to prove that there exists a constant $c>0$ such that \[ h(n) \sim c\,\Big(\frac{n}{\log n}\Big)^{1/2}\qquad (n\to\infty), \] where $\log$ is the natural logarithm.

QUICK LITERATURE/CONTEXT CHECK.
The problem text states (without proof here) that Erdős--Selfridge proved the order of magnitude $h(n)\asymp (n/\log n)^{1/2}$. It also reports a heuristic constant $c=\sqrt{2\pi}$. I will not assume any of those results; I will only derive basic identities and provide computational sanity checks.

ATTACK PLAN.
Proof track. Express $k_p(n)$ explicitly (Legendre formula), then analyze how many distinct integers occur among $\{k_p(n)\}$ as $p$ ranges over primes $\le n$.

Reality-check track. Compute $h(n)$ for moderate $n$ and compare to $\sqrt{n/\log n}$.

WORK.
Phase 1: fast reality check (computation). Using Legendre's formula (Lemma 912.1) I computed $h(n)$ exactly for several $n$.

(These values were computed by a direct prime loop and Legendre summation; for example, $h(10^7)=2087$ and $h(3\cdot 10^7)=3503$.)

Lemma 912.1 (Legendre formula). For every prime $p\le n$, \[ k_p(n)=v_p(n!)=\sum_{j\ge 1} \Big\lfloor \frac{n}{p^j}\Big\rfloor. \]

Proof. Among the integers $1,2,\dots,n$, the number divisible by $p$ is $\lfloor n/p\rfloor$, each contributing at least one factor $p$ to the product $n!$. The number divisible by $p^2$ is $\lfloor n/p^2\rfloor$, contributing an additional factor $p$ beyond the first, and so on. Summing the contributions over all powers $p^j$ counts exactly the total exponent of $p$ in $n!$. $\square$

Lemma 912.2 (large primes have single-term exponents). If $p$ is prime and $p>\sqrt{n}$, then \[ k_p(n)=v_p(n!) = \Big\lfloor \frac{n}{p}\Big\rfloor. \]

Proof. By Lemma 912.1, \[ v_p(n!)=\Big\lfloor \frac{n}{p}\Big\rfloor + \Big\lfloor \frac{n}{p^2}\Big\rfloor+\Big\lfloor \frac{n}{p^3}\Big\rfloor+\cdots. \] If $p>\sqrt{n}$ then $p^2>n$, hence $\lfloor n/p^j\rfloor=0$ for every $j\ge 2$. Only the $j=1$ term remains. $\square$

Lemma 912.3 (a crude $O(\sqrt n)$ upper bound on $h(n)$). For every $n\ge 2$, \[ h(n) \le \lfloor \sqrt{n}\rfloor + \pi(\sqrt{n}), \] where $\pi(x)$ is the number of primes $\le x$. In particular $h(n)=O(\sqrt{n})$.

Proof. Split primes into two ranges.

$1$ Primes $p>\sqrt{n}$. By Lemma 912.2, $k_p(n)=\lfloor n/p\rfloor$. As $p$ ranges over $\{\text{primes}:\sqrt{n}<p\le n\}$, the integer $\lfloor n/p\rfloor$ lies in $\{1,2,\dots,\lfloor\sqrt{n}\rfloor\}$. Hence the set of exponents contributed by these primes has size at most $\lfloor\sqrt{n}\rfloor$.

$2$ Primes $p\le \sqrt{n}$. There are exactly $\pi(\sqrt{n})$ such primes, hence they contribute at most $\pi(\sqrt{n})$ distinct exponent values.

Taking the union of the two exponent sets proves the displayed inequality. $\square$

VERIFICATION.

• Lemma 912.1 is the standard valuation counting argument and does not use any unproved prime distribution input.
• Lemma 912.2 correctly uses $p^2>n$ to kill higher terms.
• The computation table is consistent across multiple $n$ and shows $h(n)$ growing roughly like a constant times $\sqrt{n/\log n}$, but does not constitute a proof.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: exact formulae for the exponents $k_p(n)$ (Lemma 912.1) and their simplification for $p>\sqrt{n}$ (Lemma 912.2), plus the crude bound $h(n)\le \lfloor\sqrt n\rfloor+\pi(\sqrt n)$ (Lemma 912.3). Computations up to $n=3\cdot 10^7$ give, e.g., $h(10^7)=2087$ and $h(3\cdot 10^7)=3503$, with ratios $h(n)/\sqrt{n/\log n}$ around $2.65$.

(ii) First gap (crisp): Prove the asymptotic $h(n)\sim c\sqrt{n/\log n}$ for some constant $c>0$, or even prove the existence of the limit $\lim_{n\to\infty} h(n)/\sqrt{n/\log n}$.

(iii) Top 3 next moves:

1. Analyze the map $p\mapsto v_p(n!)$ more sharply: show that for most primes $p$ in a suitable range, $v_p(n!)$ is close to $n/(p-1)$ with controllable error, and convert distinct-value counting into a question about spacing of the values $n/(p-1)$.
2. Reduce to primes in a "main range" $p\asymp \sqrt{n\log n}$ where one expects the spacing between consecutive $v_p(n!)$ to be about $1$; then show that sufficiently many integers are hit as $p$ varies.
3. Use computation to probe the constant: compute $h(n)$ for larger $n$ (say $10^8$ or beyond) and track $h(n)/\sqrt{n/\log n}$ to see whether it drifts toward a stable value.

(iv) Minimal counterexample structure (if the asymptotic were false): a mechanism causing long-range "collisions" $v_p(n!)=v_q(n!)$ for many distinct primes $p\ne q$ in the main range, or conversely large gaps of missing integers among the set $\{v_p(n!):p\le n\}$; such a mechanism would likely be tied to irregular distribution of primes in short intervals.