Skip to content

Counting non-multiples

November 12, 2007 am30 7:53 am

Sieve of EratosthenesHow 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.

11 Comments leave one →
  1. November 12, 2007 am30 8:49 am 8:49 am

    What topic was I teaching?

    Counting/overcounting? Prime factorization? Venn Diagrams? Careful Reading?

    I’m feeling too lazy to do the 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).

  2. November 12, 2007 pm30 10:23 pm 10:23 pm


    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?

  3. November 13, 2007 am30 10:46 am 10:46 am

    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.

  4. November 13, 2007 pm30 6:07 pm 6:07 pm

    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…

  5. November 14, 2007 am30 6:25 am 6:25 am

    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!

  6. David Radcliffe permalink
    November 15, 2007 am30 8:21 am 8:21 am

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

  7. November 15, 2007 am30 8:42 am 8:42 am

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

  8. November 15, 2007 am30 8:49 am 8:49 am

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

  9. April 28, 2017 pm30 12:33 pm 12:33 pm

    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 جماهير الاهلى.


  1. If you liked the last one…more 3, 5, 7 « JD2718
  2. Puzzlette: How many multiples? « JD2718

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: