# Counting non-multiples

November 12, 2007 am30 7:53 am

How many numbers from 500 to 999, inclusive, are not multiples of any of 3, 5, or 7?

Bonus: I posed this problem Monday, solved it with class on Wednesday. What topic was I teaching?

Isn’t the sieve of Eratosthenes on the left pretty? It won’t help with this problem, but seemed related. It’s actually a quilt! and the work of a strange blogger who seems to like visitors.

Advertisements

11 Comments
leave one →

What topic was I teaching?Counting/overcounting? Prime factorization? Venn Diagrams? Careful Reading?

I’m feeling too lazy to

dothe actual problem, at the moment. But the approach I’d use is to count how many multiples of 3, of 5 and of 7 and add these numbers together. Then subtract the number of multiples of 15, 21and 35 (since each of these numbers got counted twice in the first set of numbers) and finally subtract the number of multiples of 105 (since first we added them in 3 times, then subtracted them out 3 times, and now have to add them back in one more time to actually count them). To answer the question subtract the result from 500 (the number of numbers there are all together from 500 to 999 inclusive).Hi,

My number theory is pretty rusty but I think this problem is related to number theory (and to Venn diagrams) as mathmom said.

If I’m remembering correctly there’s Euler’s totient function, phi, which tells you how many numbers less than a given number are relatively prime to the number.

So, if you looked at how many numbers less than 105 (3x5x7) were relatively prime to 105 then that same count would apply to the set of numbers in the ranges 106-210, 211-315, 316-420, 421-525 and so on …

So, the numbers not divisible by 3,5, or 7 would be those relatively prime to 105. So, you could compute phi(105) and multiply that number by the number of whole 105 number ranges in the 500-999. 526-630 would be such a range. 631-735 would be another. Then 736-840 and 841-945. So, there are 4 whole 105-number ranges between 500 and 999.

So, phi(105)*4 is part of the answer but then you’d have to calculate the number of numbers not divisible by 3,5 or 7, in the ranges 500-525 and 946-999.

This whole things seems quite messy.

What’s the cute way?

Mathmom’s good here. My book calls it inclusion-exclusion, but mom’s choices work just as well. Include all. Exclude all pairs. Put back all triples. If there were more numbers to avoid, we’d go back and take out all quadruples. And so on.

Hers is the cute way. Relatively little work for an annoyingly troublesome result.

It’s not really cute. It’s still tedious. The reason why I didn’t do it is that still doing all those steps are annoying because there’s no general formula for how many multiples of m in an interval of a certain size (if you don’t believe me consider multiples of 3 in {2, 3, 4, 5} {3, 4, 5, 6}| or {4, 5, 6, 7}, for example) so you have to look at the how close you are to a multiple of m at each end of the interval, and just, yuck…

I still do think it is cute. But repeatedly adding and subtracting we know we will reach an answer – and the next best method is to create a sieve.

As far as “How many multiples of n exist on [a,b]?” I think we can treat that as a little problem. I will post!

The number of multiples of n lying between a and b is floor(b/n) – floor((a-1)/n).

As a kid I figured, round b/n down, round a/n up, subtract, add 1

David & JD, those are both certainly “cuter” than my way. :)

Hi there,I check your blog named “Counting non-multiples | JD2718” regularly.Your story-telling style is awesome, keep up the good work! And you can look our website about جماهير الاهلى.