Excluding multiples of numbers [X,Y,Z...] in a given set [1-K]

Spambot

New member
Joined
Mar 23, 2018
Messages
4
The original question was how many days in a year aren't multiples of 2, 3 and 5.
1/2 * 2/3 * 4/5= 8/30. So in 360 days, 96 days aren't multiples of 2,3 or 5 and in the last 5 days only 361 isn't a multiple of those 3 numbers. So the answer is a 97.

That isn't my problem though.
This method breaks down when I do 2,3,5,7 and 11.
1/2 * 2/3 * 4/5 * 6/7 * 10/11 = 16/77
However there are 17 numbers that aren't multiples of these numbers between 1 - 77
1, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73

I would like to know why it breaks down and maybe what the formal name of this method is called if this is actually a method.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
7,797
The original question was how many days in a year aren't multiples of 2, 3 and 5.
1/2 * 2/3 * 4/5= 8/30. So in 360 days, 96 days aren't multiples of 2,3 or 5 and in the last 5 days only 361 isn't a multiple of those 3 numbers. So the answer is a 97.
What does it mean to say "days in a year are multiples"? For example, April 11 is the 101th day of the year but is the 11th day of the month. Which number does the question mean?

 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,232
The original question was how many days in a year aren't multiples of 2, 3 and 5.
1/2 * 2/3 * 4/5= 8/30. So in 360 days, 96 days aren't multiples of 2,3 or 5 and in the last 5 days only 361 isn't a multiple of those 3 numbers. So the answer is a 97.

That isn't my problem though.
This method breaks down when I do 2,3,5,7 and 11.
1/2 * 2/3 * 4/5 * 6/7 * 10/11 = 16/77
However there are 17 numbers that aren't multiples of these numbers between 1 - 77
1, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73

I would like to know why it breaks down and maybe what the formal name of this method is called if this is actually a method.
Let's see why the method works in even a special case.

The prime factors of 360 are 2, 3, and 5.

The multiples of 2 that divide evenly into 360 number 180.

The multiples of 3 that divide evenly into 360 number 120.

The multiples of 5 that divide evenly into 360 number 72.

If I add those up, I get 372, which is clearly the wrong answer.

The reason is that I have twice counted the products of 2 and 3 in the 180 and 120. I have twice counted the products of 2 and 5 in the 180 and 72. And I have twice counted the products 3 and 5 in the 120 and 72.

2 * 3 = 6. There are 360/6 = 60 multiples of 6.

2 * 5 = 10. There are 360/10 = 36 multiples of 10.

3 * 5 = 15. There are 360/15 = 24 multiples of 15.

I add those up and get 120. So I need to subtract 120 from 372 to get 252.

Is that correct? NO!

In the 60 multiples of 6 are multiples of 30. In the 36 multiples of 10, there are multiples of 30. In the 24 multiples of 15, there are multiples of 30.

Now we included those multiples of 30 when we added the 180, the 120, and the 72. So they were counted 3 times. But when we subtracted the 120, we included those multiples of 30. So we subtracted them 3 times. So they have not been counted at all after the subtraction. We need to add them back. There are 12 of them.

372 - 120 + 12 = 264.

So the number that are not divisible by 2, 3, or 5 is 360 - 264 = 96.

This comes under the rubric of counting principles.

Now if you think about it, you can get

\(\displaystyle 96 = 360 * \dfrac{8}{30} = 360 * \dfrac{1}{2} * \dfrac{8}{15} = \dfrac{1}{2} * \dfrac{2}{3} * \dfrac{4}{5} =\)

\(\displaystyle 360 *\dfrac{2 - 1}{2} * \dfrac{3 - 1}{3} * \dfrac{5 - 1}{5}.\)

The whole reason that this works is that 2, 3, and 5 form the entire set of primes factors of 360. Once you add 7 and 11 to the mix, we have to deal with numbers that are not prime factors.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
7,797
This is an exercise in using the inclusion/exclusion rule.
\(\displaystyle [\left\lfloor {\frac{{365}}{2}} \right\rfloor + \left\lfloor {\frac{{365}}{3}} \right\rfloor + \left\lfloor {\frac{{365}}{5}} \right\rfloor - \left\lfloor {\frac{{365}}{6}} \right\rfloor - \left\lfloor {\frac{{365}}{{10}}} \right\rfloor - \left\lfloor {\frac{{365}}{{15}}} \right\rfloor + \left\lfloor {\frac{{365}}{{30}}} \right\rfloor=268 \) SEE HERE
Note that \(\displaystyle 365-268=97\)

To extend this to a new set : Add \(\displaystyle \{2,3,5,7,11\}\) that on at a time; then subtract \(\displaystyle \{3,10,14,22,15,21,33,35,55,77\}\) that is two at a time; then add back \(\displaystyle \{30,70,14\cdot 11,105,55\cdot 11\}\) that is three at a time; then add four time subtract. You will see the some of those are greater than \(\displaystyle 365\) which we don't use.
 
Top