Erdős Problem #983

The problem

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)$.

Statement quoted from erdosproblems.com/983, maintained by Thomas Bloom. Original source: [Er70b,p.138]. Current status there: open.

AI contributions

As recorded in Terence Tao's wiki AI contributions to Erdős problems (data as of 30 Jun 2026). 🟢 full, 🟡 partial, ⚪ unverified, 🔴 incorrect.

Caveats

The wiki's classifications are provisional and are not a benchmark. Many Erdős problems have never had a thorough literature review, so a result that looks new may later turn out to be known; some problems were also stated ambiguously or incorrectly. See the problem page for the full discussion.

∎