Erdős Problem #371

Canonical assertion

declared status 'open'. Formalized: yes. Let $P(n)$ denote the largest prime factor of $n$. Show that the set of $n$ with $P(n)<P(n+1)$ has density $1/2$. Current best: The best unconditional lower bound available is due to L\"{u} and Wang [LuWa25], who prove that$$\#\{ n<x :P(n)<P(n+1)\} > (0.2017-o(1))x,$$and the same lower bound for the complement. Tao and Ter\"{a}v\"{a}inen [TaTe19] have proved that the asymptotic density is $1/2$ at 'almost all scales'. More generally, for any $0\leq \alpha \leq1$, Ter\"{a}v\"{a}inen [Te18] proved that the logarithmic density of the set of $n$ for which $P(n+1)>P(n)n^\alpha$ exists and is equal to$$\int_{[0,1]^2}1_{y\geq x+\alpha}u(x)u(y)\mathrm{d}x\mathrm{d}y$$where $u(x)=x^{-1}\rho(x^{-1}-1)$ and $\rho$ is the Dickman function. Wang [Wa21] has proved the same value holds for the asymptotic density (and in particular provided an affirmative answer to the original question) conditional on the Elliott-Halberstam conjecture for friable integers. Prize: no. OEIS: A070089. Tags: number theory.