Is $f(n,k)=(1-\rho(\alpha)+o(1))k$ for the count of $n+i$ with prime factor $>k$? (Erdős #1184)
Statement
For positive integers $n$ and $k$, let $P(m)$ denote the largest prime factor of $m$, and let $f(n,k)$ count the number of indices $1\leq i\leq k$ for which $P(n+i)>k$. Let $\rho$ be the Dickman function (the asymptotic density of smooth numbers, $\rho(\alpha)=\lim_{x\to\infty}\Psi(x,x^{1/\alpha})/x$). Is it true that whenever $\alpha>1$ satisfies $n=k^{\alpha+o(1)}$, one has $$f(n,k)=(1-\rho(\alpha)+o(1))\,k?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written proof) that $f(n,k)=(1-\rho(\alpha)+o(1))k$ for all $\alpha>1$ with $n=k^{\alpha+o(1)}$. ADVANCES: prove the asymptotic for a new range of $\alpha$ — in particular any nontrivial two-sided bound in the range $\alpha\geq 2$, where the background records none — or strengthen Erdős's one-sided bounds (improve the constant $c_\alpha$ in the lower bound, or extend the upper bound $f(n,k)<(\alpha-1+o(1))k$ beyond $1<\alpha<2$). A reproducible large-scale computation certifying agreement of $f(n,k)/k$ with $1-\rho(\alpha)$ over a stated range of $(n,k)$ supports but does not by itself settle the conjecture. Deliver the proof, or the computation code plus the ranges covered and the measured $f(n,k)/k$ versus $1-\rho(\alpha)$.
Background
Posed by Erdős [Er76e, p.272]; listed as open on erdosproblems.com/1184 (fetched 2026-07-21, status 'open'). Erdős himself proved partial bounds: for every $\alpha>1$, if $k$ is large and $n>k^\alpha-k$ then $f(n,k)>(1-\tfrac1\alpha+c_\alpha)k$ for some constant $c_\alpha>0$; and for $1<\alpha<2$ with $n\leq k^\alpha-k$, $f(n,k)<(\alpha-1+o(1))k$. He knew of no nontrivial bounds for $\alpha\geq 2$. Ramachandra, Shorey, and Tijdeman [RST75b] proved that if $n>\exp(c(\log k)^2)$ for a constant $c>0$ then $f(n,k)\geq k-\pi(k)$. The conjecture asserts that the exact main term is governed by the Dickman function $\rho$. No cash prize is attached. Attacker's tool: direct computation of $f(n,k)$ for large $n,k$ across chosen $\alpha$ (sieve or factor each $n+i$ for its largest prime factor) compared against $(1-\rho(\alpha))k$ using numerically evaluated $\rho$, backed by smooth-number (Dickman–de Bruijn) analytic machinery to attack the $\alpha\geq 2$ range.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1184 (T. F. Bloom) | website |
| REF-02 | Dickman function (definition of $\rho$) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.