Problem 983

Erdős Problem #983: declared status 'open'. Formalized: no. 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 at least $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)$. Prize: no. Tags: number theory.