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

Erdős problem #912 — wave 7t

Accessed 2026-07-28. Companion verifier: runs/erdos912_wave7t_reverify.py.

Outcome

(a) Elementary-rigorous: I prove the conjectural observation in the

newest tracker comment, uniformly: \[ \boxed{\lvert h(n+1)-h(n)\rvert\leq 1\quad\text{for every }n\geq 1.} \]

(a) Elementary-rigorous: I give an exact formula not only for \(h(n)\)

but for every representative multiplicity \(u_r(n)\), reducing the problem to prime counts in the disjoint harmonic intervals \((n/(k+1),n/k]\).

(b) Rigorous modulo the prime number theorem: after discarding two

quantitatively controlled tails, the original problem is exactly a deterministic logarithmic-scale prime-void problem. I state the precise missing lemma below.

(c) Heuristic only: a direct recalculation of the Cramér model gives

\[ c_r=\frac{\Gamma(r-\tfrac12)}{\sqrt2\,r!} =\sqrt{2\pi}(-1)^{r+1}\binom{1/2}{r}, \] not the \(\binom{2-\sqrt2}{r}\) displayed in the 2026 tracker comment. This corrects the output of that model; it is not an unconditional asymptotic for the primes.

(d) Computational-only: three independent exact evaluations agree at

all displayed powers of ten through \(10^9\), where \[ h(10^9)=18233. \]

The main asymptotic is not proved here.

0. Mandatory live-page check

(d, browser-verified page observation.) I fetched the live problem page and its discussion thread through the Bright Data browser path on 2026-07-28, before doing any mathematics. The page showed:

status OPEN;
0 claimed proofs;
Currently working on this problem: None;
Interested in collaborating: None;
two comments, by TerenceTao (2025-08-31) and Owmire09 (2026-06-24);
likes from Alfaiz, ebarschkis, and Owmire09;
“This problem looks difficult”, “looks tractable”, both formalisation-work

markers, and the remaining non-like participation markers all None.

Thus the requested stop condition did not fire.

Verbatim live statement

If \[ > n! = \prod_i p_i^{k_i} > \] is the factorisation into distinct primes then let \(h(n)\) count the number of distinct exponents \(k_i\).
Prove that there exists some \(c>0\) such that \[ > h(n) \sim c \left(\frac{n}{\log n}\right)^{1/2} > \] as \(n\to \infty\).

Everything mathematical listed on the live page

(b, source-verified.) The page attributes the problem to Erdős and

Selfridge and records their theorem \[ h(n)\asymp (n/\log n)^{1/2}. \]

(c, explicitly heuristic on the page.) Tao's comment deletes the

Legendre tail, focuses on primes \(p\asymp\sqrt{n\log n}\), and applies the Cramér model to \((n/(k+1),n/k]\). It predicts \[ c=\int_0^\infty(1-e^{-2/t^2})\,dt=\sqrt{2\pi}. \] His edit notes the exact floor-quotient identity discussed below.

(c, unverified tracker comment.) Owmire09 defines

\[ u_r(n)=\#\{k:\#\{p\leq n:\nu_p(n!)=k\}=r\}, \] writes \(h(n)=\sum_{r\geq1}u_r(n)\) and \(\pi(n)=\sum_{r\geq1}r\,u_r(n)\), and proposes \[ u_r(n)\sim c_r\sqrt{n/\log n},\qquad c_r=\sqrt{2\pi}(-1)^{r+1}\binom{2-\sqrt2}{r}. \]

(d, claimed computation in an unverified tracker comment.) The same

comment reports that a computation through \(10^8\) found \(h(n+1)-h(n)\in\{-1,0,1\}\), and conjectures this always holds. A uniform proof is given below.

The site itself warns that comments are not verified for correctness.

1. Primary-source literature check

(b, source-verified.) P. Erdős,

“Miscellaneous problems in number theory”, Congressus Numerantium 34 (1982), 25–45, states this as Theorem 1 on pp. 25–27. Erdős and Selfridge prove the two-sided order bound and say that obtaining an asymptotic appears to require information about consecutive prime differences that was unavailable.

(b, source-verified.) R. Heyman and M. R. Miraj,

“On Some Floor Function Sets,” arXiv:2309.16072v4 (2024), Theorem 2 and its proof, prove \[ h(n)=\left|\{\lfloor n/p\rfloor:p\leq n,\ p\ {\rm prime}\}\right|. \] Their theorem restates the Erdős–Selfridge order bound after this identity. I give a self-contained proof, strengthened to preserve all multiplicities \(u_r\), in §2.

(d, source-verified database entry.)

OEIS A071626 is exactly this sequence. It links both sources above and a table through \(n=10000\). It is used only as a data cross-check, not as proof.

(b, checked but not a solution to this problem.) C. Sanna,

arXiv:1902.09224, studies the distribution over general integers \(m\) of the number of distinct exponents in \(m\), not the factorial subsequence \(m=n!\), and does not supply the requested asymptotic.

(b, relevant background rather than a solution.) P. X. Gallagher,

“On the distribution of primes in short intervals”, Mathematika 23 (1976), 4–9, proves a Poisson law for a randomly placed interval of length \(\lambda\log x\), conditional on a uniform Hardy–Littlewood prime-tuple conjecture. A current extension, A. Jha, arXiv:2605.23014 (2026), treats growing \(\lambda\) under a stronger Hardy–Littlewood hypothesis. Neither paper proves the deterministic harmonic-grid lemma in §4.

(d, honest search result.) Exact-phrase, title, OEIS, arXiv-ID, and citation searches found no primary source claiming the asymptotic in the live statement. This is a report of the searches performed, not a claim that no uncatalogued result exists.

2. Exact multiplicity-preserving reduction

Let

m=\lfloor\sqrt n\rfloor,\qquad R_{n,k}:= \pi(\lfloor n/k\rfloor) -\pi\!\left(\max\{m,\lfloor n/(k+1)\rfloor\}\right) \quad(1\leq k\leq m).

Thus \(R_{n,k}\) is exactly the number of primes \(p>\sqrt n\) for which \(\lfloor n/p\rfloor=k\).

Theorem

(a) Elementary-rigorous. For every \(n\geq2\) and \(r\geq1\),

\boxed{\quad u_r(n)=\mathbf 1_{r=1}\pi(m) \#\{1\leq k\leq m:R_{n,k}=r\}. \quad} \tag{2.1}

Consequently,

\boxed{\quad h(n)=\pi(m)+\sum_{k=1}^{m}\mathbf 1_{R_{n,k}>0}. \quad} \tag{2.2}

Proof

(a) If \(p<q\leq\sqrt n\) are primes, then

\frac np-\frac nq=\frac{n(q-p)}{pq}>1,

because \(pq<q^2\leq n\). Hence \(\lfloor n/p\rfloor>\lfloor n/q\rfloor\). Legendre's formula

\nu_p(n!)=\sum_{j\geq1}\lfloor n/p^j\rfloor

then also gives \(\nu_p(n!)>\nu_q(n!)\): the \(j=1\) term is strictly larger and every later term is non-increasing as \(p\) increases. Thus the primes \(p\leq\sqrt n\) give \(\pi(m)\) distinct singleton values in both models.

(a) These small-prime values cannot collide with a value from \(q>\sqrt n\). Indeed, writing \(n=m^2+s\), \(0\leq s\leq2m\), a direct division into the cases \(s<m\) and \(s\geq m\) gives

\left\lfloor\frac nm\right\rfloor > \left\lfloor\frac n{m+1}\right\rfloor.

Therefore, for integers \(p\leq m<q\), \(\lfloor n/p\rfloor>\lfloor n/q\rfloor\); the same separation holds for the Legendre exponents.

(a) Finally, if \(p>\sqrt n\), then \(p^2>n\), so Legendre's formula is exactly

\nu_p(n!)=\lfloor n/p\rfloor.

For a fixed \(k\), the relevant primes are precisely

\max\{m,\lfloor n/(k+1)\rfloor\}<p\leq\lfloor n/k\rfloor,

whose number is \(R_{n,k}\). This proves (2.1), and summing its support proves (2.2). \(\square\)

This proof also independently verifies the Heyman–Miraj cardinality identity; it does not assume that paper.

3. A uniform theorem resolving the newest comment's conjecture

Theorem

(a) Elementary-rigorous. For every \(n\geq1\),

\boxed{\lvert h(n+1)-h(n)\rvert\leq1.} \tag{3.1}

Proof

By §2 it is enough to use

F_n=\{\lfloor n/p\rfloor:p\leq n,\ p\ {\rm prime}\}, \qquad h(n)=|F_n|.

Put \(N=n+1\).

(a), nonsquare case. Suppose \(N\) is not a square and put \(m=\lfloor\sqrt N\rfloor=\lfloor\sqrt{N-1}\rfloor\). For each of \(N-1\) and \(N\), the denominators \(p\leq m\) contribute exactly \(\pi(m)\) distinct values, disjoint from those with \(p>m\). Their numerical values may move, but their contribution to the cardinality is fixed.

For an existing prime \(p>m\),

\left\lfloor\frac Np\right\rfloor =\left\lfloor\frac{N-1}{p}\right\rfloor+\mathbf 1_{p\mid N}. \tag{3.2}

There is at most one prime divisor \(p>m\) of \(N\), since two such distinct prime divisors would have product at least \((m+1)(m+2)>N\). If \(N\) is prime, the only change instead is the addition of the new denominator \(p=N\). Hence the large-prime value set is obtained by changing or adding at most one generating value, so its cardinality changes by at most one.

(a), square case. Now suppose \(N=m^2\). If \(m\) is composite, the small-prime denominator set does not change at the threshold, and no prime \(p>m\) divides \(m^2\). The two cardinalities are equal.

If \(m\) is prime, let

T=\{\lfloor (m^2-1)/p\rfloor:p>m,\ p<m^2,\ p\ {\rm prime}\}.

No \(p>m\) divides \(m^2\), so this is also the large-prime value set at \(m^2\). The denominator \(p=m\) moves from the large side to the small side, and

h(m^2-1)=\pi(m)-1+|T\cup\{m-1\}|,\qquad h(m^2)=\pi(m)+|T|.

Their difference is \(0\) or \(1\). The finitely many initial cases are immediate. This proves (3.1). \(\square\)

The proof explains why many prime factors of \(N\) do not cause a large jump: all small-prime exponents remain a block of singleton representatives, while at most one prime factor can lie above \(\sqrt N\).

4. Exact isolation of the remaining asymptotic

Put

L=L_n=\sqrt{\frac n{\log n}},\qquad A_n(k)=\mathbf1_{R_{n,k}>0}.

For fixed \(0<a<b<\infty\), define the central occupancy statistic

H_n(a,b)=\frac1L \sum_{\lceil aL\rceil\leq k\leq\lfloor bL\rfloor}A_n(k).

Rigorous tail removal

(a) The omitted range \(k<aL\) contains at most \(aL+1\) occupied bins.

(a) Every occupied bin with \(k>bL\) contains a distinct prime

\sqrt n<p<\frac{n}{bL},

because the harmonic bins are disjoint. Its contribution is therefore at most \(\pi(n/(bL))\).

(b), using the prime number theorem.

\frac{\pi(\sqrt n)}L\longrightarrow0,\qquad \frac{\pi(n/(bL))}L\longrightarrow\frac2b.

Consequently the two discarded tails have relative limsup at most

a+\frac2b. \tag{4.1}

Thus the problem is concentrated, with an explicit vanishing double-tail error, on \(k=tL\) for fixed \(t\in(0,\infty)\).

The exact missing lemma for the predicted constant

The sufficient statement is:

\boxed{\quad H_n(a,b)\longrightarrow \int_a^b(1-e^{-2/t^2})\,dt \quad\text{for every fixed }0<a<b<\infty. \quad} \tag{H}

(b) If (H) holds, (4.1), followed by \(a\downarrow0\) and \(b\uparrow\infty\), gives

\frac{h(n)}{L}\longrightarrow \int_0^\infty(1-e^{-2/t^2})\,dt=\sqrt{2\pi}. \tag{4.2}

The integral evaluation is elementary (integration by parts followed by \(y=\sqrt2/t\)).

(c) Why (H) is the Cramér prediction: at \(k=tL\),

\left|\left(\frac n{k+1},\frac nk\right]\right| \sim\frac{\log n}{t^2}, \qquad \log(n/k)\sim\tfrac12\log n.

The model therefore gives a Poisson mean \(2/t^2\), and hence occupied probability \(1-e^{-2/t^2}\).

(a/b) Formula (2.2) plus (4.1) is a clean unconditional reduction. Statement (H) is the precise unproved prime-distribution input; it is not smuggled into the calculation.

5. Audit of the multiplicity heuristic

(c) The same Cramér calculation predicts, for fixed \(r\geq1\),

\frac{u_r(n)}L\ \leadsto\ \int_0^\infty e^{-2/t^2}\frac{(2/t^2)^r}{r!}\,dt. \tag{5.1}

The small-prime singleton term \(\pi(\sqrt n)/L\) tends to zero, so it does not alter the conjectural limit.

(a, evaluation of the model integral.) With \(\lambda=2/t^2\),

\begin{aligned} c_r &=\frac1{\sqrt2\,r!}\int_0^\infty e^{-\lambda}\lambda^{r-3/2}\,d\lambda\\ &=\frac{\Gamma(r-\tfrac12)}{\sqrt2\,r!} =\sqrt{2\pi}(-1)^{r+1}\binom{1/2}{r}. \tag{5.2} \end{aligned}

Moreover, Tonelli's theorem for the nonnegative terms gives

\sum_{r\geq1}c_r =\int_0^\infty(1-e^{-2/t^2})\,dt =\sqrt{2\pi},

as required by Tao's total heuristic.

(c, diagnosis.) The live comment instead has \(1/2\) replaced by \(2-\sqrt2\). Those constants also happen to sum to \(\sqrt{2\pi}\), by the binomial series, but they are not the probabilities obtained from a Poisson variable of mean \(2/t^2\). The companion program independently checks (5.1) by numerical quadrature and checks (5.2) by the gamma formula. This is a correction to a heuristic comment, not a disproof of any theorem.

6. Exact computation

Values of \(h(n)\)

(d) Computational-only. Here \(L=\sqrt{n/\log n}\). Every row was computed in three ways: Legendre exponents, distinct floor quotients, and the interval formula (2.2).

\(n\)	\(\pi(n)\)	\(h(n)\)	\(L\)	\(h(n)/L\)	\(h(n)/(\sqrt{2\pi}L)\)
\(10^2\)	25	11	4.659906	2.360563	0.941728
\(10^3\)	168	31	12.031826	2.576500	1.027875
\(10^4\)	1,229	87	32.950511	2.640323	1.053337
\(10^5\)	9,592	252	93.198120	2.703917	1.078707
\(10^6\)	78,498	723	269.039799	2.687335	1.072091
\(10^7\)	664,579	2,087	787.667880	2.649594	1.057035
\(10^8\)	5,761,455	6,169	2,329.953009	2.647693	1.056277
\(10^9\)	50,847,534	18,233	6,946.577750	2.624746	1.047122

These finite values are consistent with \(\sqrt{2\pi}\), but no finite table proves convergence.

Multiplicity spectrum at \(n=10^9\)

(d) Computational-only.

\(r\)	exact \(u_r(10^9)\)	\(u_r/L\)	direct Cramér \(c_r\)	live-comment constant
1	10,249	1.475403	1.253314	1.468349
2	2,026	0.291654	0.313329	0.304105
3	993	0.142948	0.156664	0.143356
4	632	0.090980	0.097915	0.086523
5	460	0.066220	0.068541	0.059082
6	319	0.045922	0.051405	0.043467
7	270	0.038868	0.040390	0.033620
8	223	0.032102	0.032817	0.026955

(d/c) At this still-small scale, \(u_1\) contains \(\pi(\sqrt{10^9})=3401\) guaranteed small-prime singletons. Removing them gives \(6848/L=0.985809\). Since the omitted term decays only like \(2/\sqrt{\log n}\), the raw \(u_1/L\) value cannot discriminate between the two proposed limiting constants.

7. Reproduction and independent checks

The standalone standard-library checker is runs/erdos912_wave7t_reverify.py.

Full reported run:

/usr/bin/time -v python3 runs/erdos912_wave7t_reverify.py \
  --max-n 1000000000 --exhaustive 10000

(d) The final-source rerun completed successfully in 66.94 wall-seconds (66.14 user seconds) with maximum RSS 827,104 KB. The default \(10^8\) run takes about 7.5 seconds and 105 MB.

The program independently:

constructs an odd-only Eratosthenes sieve from scratch and checks

\(\pi(10^j)\) against standard exact checkpoints;

updates the factorisation of \(n!\) and checks every \(1\leq n\leq10000\)

against the floor-quotient definition;

checks the first 100 terms against the live-linked OEIS data;
verifies at every table point that the complete \(u_r\) spectra agree

under Legendre exponents, floor quotients, and interval prime counts;

verifies \(\max_{n\leq10000}|h(n+1)-h(n)|=1\) (only a check—the proof in

§3 is uniform);

verifies the model integrals both by adaptive quadrature and by the gamma

closed form.

No external number-theory package or probabilistic primality test is used.

8. Precise wall

(a/b) The unresolved task is not Legendre's tail: §2 removes it exactly. It is not estimating the total number of primes: the prime number theorem is enough for the tails. The exact missing input is the zero-count statistic (H) for the deterministic, \(n\)-dependent harmonic partition at interval length \(\asymp\log n\).

(b) The ordinary PNT controls only the first moment. Sieve upper/lower bounds recover the correct order of magnitude but do not give the exact proportion of empty logarithmic intervals. Gallagher's conditional Poisson theorem averages a moving interval over all starting integers; it does not, without an additional uniform transfer theorem, control this sparse deterministic set of endpoints \(n/(k+1)\) for every \(n\).

(b) Even the Riemann hypothesis does not resolve this scale: around \(x\asymp\sqrt{n\log n}\), its standard pointwise prime-counting error is of order \(\sqrt{x}\log x\), vastly larger than an interval of length \(\asymp\log n\) containing only \(O(1)\) expected primes. A suitably uniform Hardy–Littlewood/Poisson void theorem along the harmonic grid is the named missing lemma.

(d, cost estimate.) Scaling the same literal full-sieve checker from \(10^9\) to \(10^{10}\) would require roughly 8–9 GB peak memory and about 0.2–0.3 core-hours; it was not run because that exceeds the requested few-minute regime. A monolithic \(10^{12}\) version would require hundreds of GB and roughly 20 core-hours by the measured scaling. Segmentation can reduce memory, but no finite extension supplies the uniformity needed for (H).

PARTIAL: Proved the uniform bound |h(n+1)-h(n)|<=1, gave an exact multiplicity/short-interval reduction and a three-way exact table through 10^9; the main asymptotic remains open at the stated harmonic-bin Poisson lemma.

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