How to find the total count of numbers that are divisible by some specific numbers

Question

How can I find the total count of numbers from 1 to N that are divisible by four numbers? let's say n1, n2, n3, n4.

So, for 2 3 4 5 I should get 17 as result for the range 1 to 24.

But the problem is that some numbers are I'm counting double or more times. for example it could be (N/n1) + (N/n2) + (N/n3) + (N/n4) but with repetition.

Answer 1

Let

$$A_{k,N} := \{ n \in \{1,2,\cdots,N\} \mid k \text{ divides } n \}$$

Given $n_1,\cdots,n_k$ you want to examine (i.e. you want the numbers in $[1,N] \cap \mathbb{N}$ divisible by at least one of the $n_i$), you seek

$$\left| \bigcup_{i=1}^k A_{n_i,N} \right|$$

From here, you can apply inclusion-exclusion, to express things in terms of the $A_{n_i,N}$ and the intersections thereof. Some items of note:

• $|A_{n,N}| = \lfloor N/n \rfloor$
• $A_{n,N} \cap A_{m,N} = A_{\text{lcm}(m,n),N}$

Justifying these facts and pulling these facts together with inclusion-exclusion to conclude is a task I'll leave to you.