Find the number of integers between 1 to 10000 if?

[Question]

a) divisible by at least one of 3, 5, 7, 11

b) divisible by 3 and 5 but not by 7 or 11

c) divisible by exactly three of 3, 5, 7, 11

d) divisible by at most three of 3, 5, 7, 11

[Difficulty]

I have worked on part a) but I am unable to find the answers to b, c

and d parts of the question.

[Thoughts]

A = {n| 1 <= n <= 10000, 3| n}

B = {n| 1 <= n <= 10000, 5| n}

C = {n| 1 <= n <= 10000, 7| n}

D = {n| 1 <= n <= 10000, 11| n}

|A| = floor(10000/3) = 3333

|B| = floor(10000/5) = 2000

|C| = floor(10000/7) = 1428

|D| = floor(10000/11) = 909

|AnB| = floor(10000/15) = 666

|AnC| = floor(10000/21) = 476

|AnD| = floor(10000/33) = 303

|BnC| = floor(10000/35) = 285

|BnD| = floor(10000/55) = 181

|CnD| = floor(10000/77) = 129

|AnBnC| = floor(10000/105) = 95

|AnBnD| = floor(10000/165) = 60

|AnCnD| = floor(10000/231) = 43

|BnCnD| = floor(10000/385) = 25

|AnBnCnD| = floor(10000/1155) = 8

a)

|AuBuCuD| =

|A|+|B|+|C|+|D|-|AnB|-|AnC|-|AnD|-BnC|-|BnD|-|CnD|+|AnBnC|+|AnBnD|+|AnCnD|+

|BnCnD|-|AnBnCnD|

= 3333+2000+1428+909-666-476-303-285-181-129+95+60+43+25-8

= 5845

2 Answers

Relevance
  • ?
    Lv 5
    1 decade ago
    Favorite Answer

    Good application of Inclusion / Exclusion.

    Thoughts on B)

    Intersection of 3 | n and 5 | n is clearly 15 | n because 3 and 5 are relatively prime.

    I'm going to imagine for a moment that it wants you to find all 15 | n but not 7 | n, and then incorporate 11 | n later.

    Include all 15 | n, then exclude all 15*7 | n. Can you see why this works?

    Now addressing 11 | n as well. Starting from the beginning:

    Include all 15 | n, then exclude all 15*7 | and exclude all 15*11 | n, then include all 15*7*11 | n.

    Should be (10,000 / 15) - (10,000 / (15*7) ) - (10,000 / (15*11) ) + (10,000 / (15*7*11) )

    Now let's work on C)

    I think we can split this into four separate cases (it's obvious what those cases are).

    Case 1: Divisible by 3, 5, and 7, but not 11.

    Include all 3*5*7 | n and then exclude all 3*5*7*11 | n.

    Case 2: Divisible by 3, 5, and 11, but not 7.

    Include all 3*5*11 | n and then exclude all 3*5*7*11 | n.

    It's clear how to proceed from here. You should then be able to add up the four cases to get your result.

    Last, but certainly not least, problem D)

    Include all 1 | n and then exclude all 3*5*7*11 | n. Simple. =)

    Good luck.

  • 5 years ago

    If you know that the 99th triangle number is 4950 then you know that there are 99 from 1 to 5000. The next triangle number is 5050. The formula for triangle numbers is n(n + 1)/2 To find how many triangle numbers are up to any total T you solve n(n + 1)/2 = T ----> n^2 + n - 2T = 0 by the quadratic formula and take the nearest integer below the value of n that emerges. You are right about the pattern of even / odd which means they repeat in sets of 4. Therefore there are 12 pairs of even and 12 pairs of odd in the first 48 triangle numbers.

Still have questions? Get your answers by asking now.