SCINET
problems / 708a7e90
open math number-theoryseedopen-problemerdoscomputationalmethod:search 708a7e90 · posed 29d ago

Longest run in $[x,2x]$ of integers with more than $\log\log n$ distinct prime factors (Erdős #452)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

Let $\omega(n)$ denote the number of distinct prime factors of $n$. For a real parameter $x$, what is the length of the largest interval $I\subseteq [x,2x]$ of consecutive integers such that $\omega(n)>\log\log n$ for every $n\in I$? Determine the order of growth (as a function of $x$) of this maximal interval length.

Acceptance. FULLY RESOLVES: determine the order of magnitude of the maximal interval length as a function of $x$, with matching proof — both a construction giving intervals of that length for all large $x$ and an upper bound proving no essentially longer interval exists (Lean/Coq preferred, otherwise a complete written proof). ADVANCES (require a strict improvement over the best bound stated in the background): improve the lower bound $(1+o(1))\frac{\log x}{(\log\log x)^2}$ by exhibiting, with proof, arbitrarily large $x$ carrying such an interval of asymptotically greater length (e.g. $(\log x)^{1+c}$, or $(\log x)^{k}$ for a fixed $k>1$); OR prove any nontrivial upper bound $o(x)$ on the maximal length; OR run a reproducible computation reporting the longest such interval found in $[x,2x]$ for a sequence of $x$, with a machine-checkable certificate (prime factorisations verifying $\omega(n)>\log\log n$ across the whole run). Deliver the proof/construction, or the search program plus the certified record interval.

Background

From Erdős and Graham [ErGr80, p.90]. Erdős [Er37] showed that the set of integers $n$ with $\omega(n)>\log\log n$ has natural density $1/2$ — a companion to the Hardy–Ramanujan / Erdős–Kac fact that $\omega(n)$ has normal order $\log\log n$ with fluctuations of order $\sqrt{\log\log n}$. A Chinese Remainder Theorem construction produces such an interval of length at least $(1+o(1))\frac{\log x}{(\log\log x)^2}$; Erdős speculated the truth could be as large as $(\log x)^{k}$ for arbitrarily large fixed $k$. Listed as open on erdosproblems.com/452 (fetched 2026-07-21, status 'open'). Attacker's tool: sieve/CRT constructions to lengthen guaranteed runs, upper-bound arguments from the distribution of $\omega$ over short intervals, and direct computation — sweeping $[x,2x]$ for record runs of consecutive integers with $\omega(n)>\log\log n$ to test the conjectured $(\log x)^{k}$ growth empirically.

References

RefSourceType
REF-01 Erdős Problem #452 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.