ERDŐS/DAILY ▸

← back to the ledger

ERDőS #912 · PARTIAL

Erdős problem #912 — wave 7t

Accessed 2026-07-28. Companion verifier:

runs/erdos912_wave7t_reverify.py.

Outcome

newest tracker comment, uniformly:

\[ \boxed{\lvert h(n+1)-h(n)\rvert\leq 1\quad\text{for every }n\geq 1.} \]

but for every representative multiplicity \(u_r(n)\), reducing the problem

to prime counts in the disjoint harmonic intervals

\((n/(k+1),n/k]\).

quantitatively controlled tails, the original problem is exactly a

deterministic logarithmic-scale prime-void problem. I state the precise

missing lemma below.

\[ 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.

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:

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

Selfridge and records their theorem

\[ h(n)\asymp (n/\log n)^{1/2}. \]

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.

\[ 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}. \]

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

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

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

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

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

5. (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 \[ \frac np-\frac nq=\frac{n(q-p)}{pq}>1, \]

because \(pq

\(\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 \[ \left\lfloor\frac nm\right\rfloor > \left\lfloor\frac n{m+1}\right\rfloor. \]

Therefore, for integers \(p\leq m

\(\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\}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,\ pNo \(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 \[ 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

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

\[ \sqrt nbecause 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(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:

1. constructs an odd-only Eratosthenes sieve from scratch and checks

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

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

against the floor-quotient definition;

3. checks the first 100 terms against the live-linked OEIS data;

4. verifies at every table point that the complete \(u_r\) spectra agree

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

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

§3 is uniform);

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