Or/Not Conditions in Number Theory How many positive integers, not exceeding 100, are multiples of 2 or 3 but not 4?
Hello, I was wondering how to solve problems like these. My thoughts are to count the number that are multiples of 2 but not 4, multiples of 3 but not 4, and then multiples of 6 but not 4, then use Principle of Inclusion and Exclusion as follows:
$$\left\lfloor \frac{100}{2} \times \frac{1}{2} \right\rfloor + \left\lfloor \frac{100}{3} \times \frac{3}{4} \right\rfloor - \left\lfloor \frac{100}{6} \times \frac{1}{2} \right\rfloor = 42,$$
but I am unsure as to if this is a valid solution. Can anybody confirm/deny that I am using Principle of Inclusion and Exclusion properly? Thanks!
 A: What you did is not quite correct, although it does give the correct result. This is because each floor function in inclusion-exclusion is for just one set of divisions only, not multiple ones combined as you did, although combining them still sometimes gives the same values anyway, as it does in your case. An example where it doesn't work is if $102$ were used instead, since there are $26$ multiples of $2$ but not $4$, but your technique gives $\left\lfloor \frac{102}{4} \right\rfloor = 25$. Instead, as shown in \eqref{eq1A} below, using inclusion-exclusion appropriately gives $\left\lfloor \frac{102}{2} \right\rfloor - \left\lfloor \frac{102}{4} \right\rfloor = 51 - 25 = 26$.
The procedure you seem to be following is to start with the number of multiples of $2$, but not $4$. Next, add the number of multiples of $3$, but not $12$. Finally, since you double counted these, subtract the number of multiples of $6$, but not $12$. The principle of inclusion and exclusion then gives
$$\begin{equation}\begin{aligned}
& \left(\left\lfloor \frac{100}{2} \right\rfloor - \left\lfloor \frac{100}{4} \right\rfloor \right) + \left(\left\lfloor \frac{100}{3} \right\rfloor - \left\lfloor \frac{100}{12} \right\rfloor \right) - \left(\left\lfloor \frac{100}{6} \right\rfloor - \left\lfloor \frac{100}{12} \right\rfloor \right) \\
& = (50 - 25) + (33 - 8) - (16 - 8) \\
& = 25 + 25 - 8 \\
& = 42
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
FYI, here's a bit simpler way to solve the problem. As you did, start with those numbers which are multiples of $2$ but not $4$, i.e., $2x$ with $x \in \{1, 3, \ldots, 49\}$, of which there are $25$ integers. Next, since it's a disjoint subset, you can just add the number of odd multiples of $3$, i.e., $3x$ with $x \in \{1, 3, \ldots, 33\}$, so there's $17$ of them. This then gives the same result as yours, i.e.,
$$25 + 17 = 42 \tag{2}\label{eq2A}$$
Note you can also get the same thing using inclusion-exclusion. This is done by, after dealing with the multiples of $2$ but not $4$, then adding the number of multiples of $3$ but not $6$, giving
$$\begin{equation}\begin{aligned}
& \left(\left\lfloor \frac{100}{2} \right\rfloor - \left\lfloor \frac{100}{4} \right\rfloor \right) + \left(\left\lfloor \frac{100}{3} \right\rfloor - \left\lfloor \frac{100}{6} \right\rfloor \right) \\
& = (50 - 25) + (33 - 16) \\
& = 25 + 17 \\
& = 42
\end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Also note that \eqref{eq1A} is basically the same as \eqref{eq3A} since the two $\left\lfloor \frac{100}{12} \right\rfloor = 8$ terms cancel each other out.
A: It sounds correct, but it needs unpacking.
$$\frac{100}{2} \times \frac{1}{2} = \frac{100}{4} = 25$$
which gives us the 25 singly even numbers. This is below what we think the answer is, but it's a good first step.
$$\frac{100}{3} \times \frac{3}{4} = \frac{300}{12} = 25$$
Adding the two intermediate results so far brings us to 50, which is above what we think the answer is.
Okay, sorry, I'm just confused by what you're getting at here. Clearly you know that 50 is an overcount, which is why you also have
$$ -\left\lfloor \frac{100}{6} \times \frac{1}{2} \right\rfloor = -\left\lfloor \frac{25}{3} \right\rfloor = -8$$
and that adjustment brings us to what we think is the right result. But I just don't understand what this adjustment is adjusting for. I really need to get at this answer a different way before I get too hopelessly confused by this deceptively simple problem.
I verify that the $n$th singly even number is $4n - 2$. So the 25th singly even number is 98. This obviously excludes the multiples of 4, so we only need to account for the odd multiples of 3 now.
The $n$th odd multiple of 3 is $6n - 3$. So the 17th odd multiple of 3 is 99. Then 25 + 17 = 42.
So you got the right answer this time, but your method might not give the right answer for similar problems.
Some mathematicians seems to arrive at the most elegant solution as if by divine inspiration. But many of them just don't tell you about the inelegant solutions they came up first, much less the outright dead ends.
