Problem Statement
Let $n\geq 2$ and $\pi(n)<k\leq n$. Let $f(k,n)$ be the smallest integer $r$ such that in any $A\subseteq \{1,\ldots,n\}$ of size $\lvert A\rvert=k$ there exist primes $p_1,\ldots,p_r$ such that $>r$ many $a\in A$ are only divisible by primes from $\{p_1,\ldots,p_r\}$.
Is it true that\[2\pi(n^{1/2})-f(\pi(n)+1,n)\to \infty\]as $n\to \infty$?
In general, estimate $f(k,n)$, particularly when $\pi(n)+1<k=o(n)$.
Is it true that\[2\pi(n^{1/2})-f(\pi(n)+1,n)\to \infty\]as $n\to \infty$?
In general, estimate $f(k,n)$, particularly when $\pi(n)+1<k=o(n)$.
Categories:
Number Theory
Progress
It is trivial that $f(k,n)\leq \pi(n)$. Erdős and Straus [Er70b] proved that\[f(\pi(n)+1,n)=2\pi(n^{1/2})+o_A\left(\frac{n^{1/2}}{(\log n)^A}\right)\]for any $A>0$ and, for any constant $1>c>0$,\[f(cn,n)=\log\log n+(c_1+o(1))\sqrt{2\log\log n},\]where\[c=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{c_1}e^{-x^2/2}\mathrm{d}x.\]Source: erdosproblems.com/983 | Last verified: January 19, 2026