---

Claim. Write $H(x,K)$ for the least number of integers $m\le x$ divisible by no element of $A$, the minimum taken over all sets $A$ of integers greater than $1$ with $\sum_{a\in A}1/a\le K$. Ruzsa proves that for every $K\ge1$

$$\lim_{x\to\infty}\frac{\log H(x,K)}{\log x}=e^{1-K}$$

(Theorem I), so $H(x,K)=x^{e^{1-K}+o(1)}$, and that there are positive constants $c_1,c_2$ with

$$\frac{c_1x}{\log x}<H(x,1)<\frac{x}{(\log x)^{c_2}}$$

(Theorem II). For a fixed $C>1$ the exponent $e^{1-C}$ is below $1$, so some admissible $A\subseteq[2,x]$ leaves fewer than $x/(\log x)^c$ integers unsifted for every $c>0$ once $x$ is large: the answer to the question is no. For $C=1$ Theorem II gives the asked lower bound with $c=1$, and for $0<C<1$ the union bound leaves at least $(1-C)x$ integers unsifted, as the site's commentary notes. The question is therefore answered yes for $0<C\le1$ and no for $C>1$. Read for every $C>0$, the reading Erdős expected to hold, the asked bound fails, so the result is a disproof, and the positive answer for $0<C\le1$ is part of the same theorem. The source is I. Z. Ruzsa, On the small sieve. II. Sifting by composite numbers, J. Number Theory 14 (1982), no. 2, 260--268, DOI 10.1016/0022-314X(82)90051-8; the page is dated to the issue month, April 1982, as the Crossref record gives it, and the page name uses the first of the month. Library home: ruzsa_1982_small_sieve_ii_sifting_composite_numbers.

Formulation. The problem page's corrected Statement excludes $1$ from $A$, as Ruzsa's definition (1.3) does, and this claim is valued against it. Ruzsa's sets avoid $1$, so his negative answer for $C>1$ holds for the site's wording as well. Theorem II's upper bound and the upper bound of Theorem I both rest on the Schinzel--Szekeres construction, which is why the site names that example as the reason the lower bound would be best possible.

Acceptance. Refereed: the paper appeared in the Journal of Number Theory. Reviewed: the site's curator, Thomas Bloom, who is independent of the author, labels the problem SOLVED, with the page last edited 8 April 2026, and his commentary attributes the negative answer for fixed $C>1$ and the lower bound at $C=1$ to this paper, and records that Erdős acknowledged in his 1980 survey that Ruzsa's construction had overturned his expectation; on 2026-09-05 and on 2026-10-07 the thread held two comments and the proof-claim tab was empty.

Related results. Saias (1998) proves the matching upper bound $H(x,1)\ll x/\log x$, which makes the $C=1$ case sharp but does not bear on the question's lower bound. Weingartner (2025) sharpens Theorem I to the exact order $H(x,C)\asymp x^{e^{1-C}}/\log x$ uniformly for $1\le C\le Z$ (Weingartner's claim). Erdős and Ruzsa (1980) show that when $A$ consists of primes a positive proportion of the integers up to $x$ is always left unsifted; that is a restricted variant, not this question.

Depends on. No page of this wiki.