Problem Statement
Let $A$ be a finite set and\[B=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}.\]Is it true that, for every $m>n\geq \max(A)$,\[\frac{\lvert B\cap [1,m]\rvert }{m}< 2\frac{\lvert B\cap [1,n]\rvert}{n}?\]
Categories:
Number Theory
Progress
The constant $2$ would be the best possible here, as witnessed by taking $A=\{a\}$, $n=2a-1$, and $m=2a$.This problem is also discussed in problem E5 of Guy's collection [Gu04].
In [Er61] this problem is as stated above, but with $a\mid n$ in the definition of $B$ replaced by $a\nmid n$. This is most likely a typo (especially since the problem is also given as stated above in [Er66]). There have been several counterexamples given for this alternate problem. Cambie has observed that, if $A$ is the set of primes bounded above by $n$, and $m=2n$, then\[\frac{\lvert B\cap [1,m]\rvert }{m}=\frac{\pi(2n)-\pi(n)+1}{2n}\sim \frac{1}{2\log n}\]while\[\frac{\lvert B\cap [1,n]\rvert}{n}=\frac{1}{n}.\]Further concrete counterexamples, found by Alexeev and Aristotle, are given in the comments section.
Source: erdosproblems.com/488 | Last verified: January 15, 2026