Status
On this page
Status
Topics
Status
On this page
Status
Topics
Fix some constant and let be large. Let be such that for all and .
What choice of such an minimises the number of integers not divisible by any ?
Fix some constant and let be large. Let be such that for all and .
What choice of such an minimises, up to an error of as with fixed, the number of integers not divisible by any ?
Source: erdosproblems.com/783
An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.
The site labels the problem SOLVED. The corrected Statement is settled: Tao [Ta26] proved that every admissible leaves at least integers up to unsifted, and the prime tail attains that, so it minimizes up to . Claim pages: Tao 2026 (accepted, full, on the site's documented acceptance; not refereed: the author wrote on 23 February 2026 that there was no plan to publish), Hildebrand 1987 (accepted, partial: the prime case, refereed), Erdős and Ruzsa 1980, reduction to primes (claimed, partial: the reduction to primes, stated without proof), Chojecki 2026, C at most log 2 (accepted, partial) and Chojecki 2026, rigidity (claimed, partial). The exact minimizer for a given , the site's wording, is not determined by any result on record; see Notes.
The site's wording is Erdős's question in [Er73], p. 135, verbatim in substance: for 's satisfying , and (display (14.3)), "For what choice of the 's satisfying (14.3), the number of integers not divisible by any is minimal?" Read as the site words it, it asks, for each , which admissible attains the exact minimum. Erdős proposed the largest primes up to whose reciprocal sum stays within the budget (display (14.4)) and wrote that this "either gives the extremal sequence (or at least nearly gives the minimum). I made no progress with this question." The first alternative is false in general: a thread comment of 4 February 2026 (Hunter) observed that when the budget allows, the smallest prime of the tail can be swapped for the next smaller prime, which sifts more, so the tail is not always the exact minimizer; Tao's numerical experiments reported in the thread the same day found sets beating the construction for small ; and no result on record determines the exact minimizer for a given , which Tao's post of 23 February 2026 and Chojecki's Remark 31 both leave open. The site's curator reads the problem as Erdős's second alternative: the commentary (page last edited 28 May 2026) says that Tao "suggests the problem (which is likely what Erdős meant) of whether the minimum number of integers in not divisible by any is ", with the Dickman function, and labels the problem SOLVED because "Tao has resolved this question (asymptotically at least)". The evidence for that reading is Erdős's own parenthesis "or at least nearly gives the minimum", quoted in the thread on 4 February 2026 (Woett), Erdős's " large" framing, and the fact that the exact question has no clean answer once the perturbations are known. The corrected Statement adopts this reading with the smallest change to the site's words: the minimum is sought up to as with fixed. Under the corrected Statement the answer is known: the primes in , Erdős's construction (14.4), have reciprocal sum by Mertens's theorem and leave integers unsifted by Dickman's theorem, and Tao [Ta26], Theorem 1.1, proved that every admissible leaves at least , so the prime tail minimizes up to and nothing does better. Hildebrand [Hi87b], Corollary 1, had proved this when consists of primes, answering Problem 1 of Erdős and Ruzsa [ErRu80], who had asserted without a written proof (their display (1.12)) that pairwise coprime sets do no better than sets of primes up to ; Chojecki [Ch26a] proved the case , where the tail starts above and the union bound is sharp. Under the site's wording the answer is unknown: the exact minimizer for a given is not determined by any result on record, Erdős's prime tail is not always it, and the error term in is open (Tao's write-up remarks that the prime case gives and that the general error is not determined). The commentary's sentence that Chojecki "proved this is the extremal sequence when " overstates Chojecki's Theorem 1.1, which is the asymptotic form attained by the tail up to ; the exact extremal sequence is not determined for any . The standing below judges the corrected Statement; the exact-minimizer question is recorded here and on the claim pages, not as a standing.