3
$\begingroup$

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask:

How many numbers $n\leq N$ are divisible by one or more numbers in $A$.

This is a classical application of the Inclusion-Exclusion principle. Indeed, if for each $i$ we set $A_i$ to be those numbers $n\leq N$ divisible by $i$, then $A_{i_1} \cap\cdots\cap A_{i_k} = A_k$ where $k$ is the lcm of the $i_j$ and so it's easy to evaluate $$ \Big| \bigcup_{i\in A} A_i\Big| = \sum_{\emptyset\not=B\subset A} (-1)^{1+|B|} \Big| \bigcap_{i\in B} A_i\Big| $$ However, this will take around $2^{|A|}$ time and so if $A$ is large, it becomes intractable.

There is something odd in my mind though: what if $A$ is all numbers between 2 and 100? Well, then we don't need to check divisibility by 4, as checking for 2 is enough. Continuing, we see that actually we can replace $A$ be the set of primes less than 100, and I strongly suspect we can't do better (as we end up simulating a sieving method, basically). But what if $A$ is the numbers between 51 and 100? Then there seems no naive reduction, and this becomes worse than testing for the bigger set of all numbers between 2 and 100.

Is there a more sophisticated method? Especially when $A=[51,100]$ or similar examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.