Fractional overlap of 1/2 and 1/3

Question

Given a subset of the natural number sequence (positive integers starting from 1) we could say that $\frac12$ of the numbers in the set are divisible by 2.

e.g if the set were ${[1,2,3,4,5,6,7]}$ we could say that $3\frac12$ of the numbers in it are divisible by 2.

If we now wanted to work out how many numbers are divisible by 3, we could work it out as $\frac73 = 2\frac13$ and we know this is correct because if we look at the set we can see that the numbers 3 and 6 are the 2 numbers that are divisble by 3.

If we wanted to work out how many numbers are divisible by 2 OR 3. At first glace I thought I could add up the 2 fractions and then subtract the overlap.

This would then equate to $\frac12+\frac13-(\frac12*\frac13) = \frac23$

This makes sense $\frac23$ of all natural numbers are divisible by $2$ or $3$. So if we wanted to see how many numbers were divisible by $2$ OR $3$ in the set ${1,2,3,4,5,6,7,8}$ we could say $8 * \frac23 = 5\frac13$ and this makse sense because the $5$ numbers divisible by $2$ or $3$ are ${2,3,4,6,8}$

This is where I get confused, when I test this against the number 10 for example I get $10 * \frac23 = 6\frac23$ BUT there are $7$ numbers under $10$ that are divisible by both $2$ or $3$, so I was expecting the whole number component to be $7$

Please help me understand. Is it possible to create such a fraction that would tell me the number of elements in the set that are divisible by 2 or 3?

Thanks in advance

Answer 1

Of the numbers $1$ to $n$, $\lfloor n/m \rfloor$ (i.e. the greatest integer $\le n/m$) are divisible by $m$. Now $x$ is divisible by both $m_1$ and $m_2$ if and only if $x$ is divisible by $\text{lcm}(m_1, m_2)$ (the least common multiple of $m_1$ and $m_2$: this is $m_1 m_2$ if $m_1$ and $m_2$ have no common factor $> 1$). So of the numbers $1$ to $n$, $\lfloor n/m_1 \rfloor + \lfloor n/m_2 \rfloor - \lfloor n/\text{lcm}(m_1, m_2) \rfloor$ are divisible by $m_1$ or $m_2$. For example, of the numbers $1$ to $7$, there are $$\lfloor 7/2 \rfloor + \lfloor 7/3 \rfloor - \lfloor 7/6 \rfloor = 3 + 2 - 1 = 4$$ divisible by $2$ or $3$.

Since $\dfrac{n}{m} - 1 < \left\lfloor \dfrac{n}{m} \right\rfloor \le \dfrac{n}{m}$, $$ \eqalign{\dfrac{n}{m_1} + \dfrac{n}{m_2} - \dfrac{n}{\text{lcm}(m_1,m_2)} - 2 &< \left\lfloor \dfrac{n}{m_1} \right\rfloor + \left\lfloor \dfrac{n}{m_2} \right\rfloor - \left\lfloor \dfrac{n}{\text{lcm}(m_1, m_2)}\right\rfloor \cr &< \dfrac{n}{m_1} + \dfrac{n}{m_2} - \dfrac{n}{\text{lcm}(m_1,m_2)} + 1\cr}$$

Answer 2

In general, no, even if the sets are contiguous as you have here. But most sets are not contiguous numbers. For instance, how many elements of the set $S=\{1,5,7,8,11,13,15,17,\}$ are divisible by 2 or 3? For a contiguous set, the larger the number of elements in the set, the closer the 2/3 approximation gets to the real number of elements, but it won't usually be exact unless the number of elements in the set is divisible by both 2 and 3. In fact, your estimates for 7 and 8 were off by the same amount from the real answer.