Estimate $f(k,n)$: primes needed to over-cover a $k$-subset of $\{1,\ldots,n\}$ (Erdős #983)
Statement
Let $n\ge 2$ and $\pi(n)<k\le n$, where $\pi$ is the prime-counting function. Define $f(k,n)$ to be the smallest integer $r$ such that: for every $A\subseteq\{1,\ldots,n\}$ with $\lvert A\rvert=k$, there exist primes $p_1,\ldots,p_r$ for which more than $r$ elements $a\in A$ have all of their prime factors among $\{p_1,\ldots,p_r\}$ (i.e. $a$ is $\{p_1,\ldots,p_r\}$-smooth). Estimate $f(k,n)$, particularly in the range $\pi(n)+1<k=o(n)$. In particular, is it true that $$2\pi(n^{1/2})-f(\pi(n)+1,n)\to\infty$$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a proof (machine-checkable preferred, else a complete written proof) that $2\pi(n^{1/2})-f(\pi(n)+1,n)\to\infty$ (or that it stays bounded), together with a determination of the order of magnitude of $f(k,n)$ throughout the range $\pi(n)+1<k=o(n)$. ADVANCES (proof or reproducible certificate required): (a) prove the specific limit $2\pi(n^{1/2})-f(\pi(n)+1,n)\to\infty$, or a lower bound on this difference tending to infinity; (b) sharpen the Erdős–Straus asymptotic for $f(\pi(n)+1,n)$ or for $f(cn,n)$ with an improved error term; (c) obtain a new asymptotic or two-sided bound for $f(k,n)$ in an intermediate range $\pi(n)+1<k=o(n)$; or (d) compute exact values of $f(k,n)$ for small $n$ via a reproducible program with a certificate of the extremal subset. Deliver the proof/formalization, or the computation code plus certified values.
Background
Posed by Erdős and Straus [Er70b, p.138]; listed as open on erdosproblems.com/983 (fetched 2026-07-21, status 'open'). Trivially $f(k,n)\le\pi(n)$. Erdős and Straus [Er70b] proved the endpoint asymptotics $$f(\pi(n)+1,n)=2\pi(n^{1/2})+o_A\!\left(\frac{n^{1/2}}{(\log n)^{A}}\right)$$ for every $A>0$, and, for each constant $0<c<1$, $$f(cn,n)=\log\log n+(c_1+o(1))\sqrt{2\log\log n},$$ where $c_1$ is fixed by $c=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{c_1}e^{-x^2/2}\,dx$ (a Gaussian relation). The refined question — whether $2\pi(n^{1/2})-f(\pi(n)+1,n)\to\infty$ — asks for the second-order behaviour beyond the leading term, and the general estimation of $f(k,n)$ for $\pi(n)+1<k=o(n)$ interpolates between these two regimes. Attacker's tool: for small $n$, evaluate $f(k,n)$ by searching over $k$-subsets $A$ and smooth-number structure to build a data table and test the conjectured divergence, alongside the sieve / extremal-set analysis underlying the Erdős–Straus asymptotics.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #983 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.