## Trending News

# 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

- ?Lv 51 decade agoFavorite 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.