Prove the weighted shift-maximum $F(n)=\max_k\omega(n+k)\log\log k/\log k$ diverges (Erdős #1203)
Statement
Let $\omega(m)$ denote the number of distinct prime divisors of $m$, and define $$F(n)=\max_{k\geq 1}\;\omega(n+k)\,\frac{\log\log k}{\log k},$$ the maximum being taken over positive integers $k$ (the weight $\frac{\log\log k}{\log k}$ is a normalising factor, positive and tending to $0$ for large $k$). Prove that $F(n)\to\infty$ as $n\to\infty$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean preferred, otherwise a full written proof) that $F(n)\to\infty$ as $n\to\infty$; or a disproof (a proof that $F(n)$ stays bounded along an infinite set of $n$). ADVANCES: a proof of a quantitative lower bound $F(n)\geq g(n)$ with $g(n)\to\infty$ (any explicit unbounded $g$ strictly beats the trivial $F(n)\geq 1-o(1)$); or a proof that $F(n)\geq c$ for a new constant $c>1$ for all large $n$; or a reproducible computation of $F(n)$ over a large verified range, with the program and certified factorizations, mapping its growth and exhibiting the slowest-growing $n$. Deliver the proof or the improved bound / computed data with code.
Background
Posed by Erdős [Er80, p.107]. A trivial lower bound $F(n)\geq 1-o(1)$ is easy. The content of the problem is that the maximum grows without bound in $n$: for every threshold $M$, once $n$ is large enough there must be a shift $n+k$ carrying anomalously many prime factors relative to its size, enough to beat the $\frac{\log\log k}{\log k}$ normalization. Because that weight tends to $0$ while $\omega(n+k)\ll\log(n+k)/\log\log(n+k)$, the supremum is attained at a finite (effectively bounded) $k$ for each $n$, so $F(n)$ is well defined and numerically computable. Related problems on the site: Erdős #248, #679, #890 (nearby questions on $\omega$ of shifted integers and prime factors in short intervals). A Lean formalisation exists in the DeepMind formal-conjectures repository. Listed as open on erdosproblems.com/1203 (fetched 2026-07-21, status 'open'). Attacker's tool: analytic number theory on the distribution of $\omega(m)$ in short intervals (the Erdős–Kac and Turán–Kubilius circle of ideas, and prime-factor counts of consecutive integers), together with direct computation of $F(n)$ over long ranges to gather evidence and locate the slowest-growing $n$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1203 (T. F. Bloom) | website |
| REF-02 | Lean formalisation (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.