# Divisibility homework help

1. Aug 13, 2010

### Helicobacter

In a set of integers from 250 to 380, inclusive, how many are multiples of both 2 and 7?

Please tell me if I'm correct:

floor((380-250+1)/(7*2)) = 9

And in general is it always the floor of [cardinality]/[LCM]?

2. Aug 13, 2010

### Staff: Mentor

Re: Divisibility

I get 10.
On problems of this nature, the best course is to do a sanity check on your formula to see if it gives the right results.

3. Aug 13, 2010

### Helicobacter

Re: Divisibility

What formula do you use to get 10?

4. Aug 13, 2010

### Staff: Mentor

Re: Divisibility

I didn't use a formula. The numbers in this set have to be multiples of 14, so I listed all multiples of 14 between 250 and 380.

5. Aug 13, 2010

### Helicobacter

Re: Divisibility

Is there a more efficient way than brute force?

Also, what would you do if one of the numbers wasn't prime; search for multiples of the LCM in a given set?

6. Aug 13, 2010

### Staff: Mentor

Re: Divisibility

Here's a formula that gives the correct result:
$$\frac{378 - 252}{14} + 1$$

252 is the smallest multiple of 14 that is greater than 250. 378 is the largest multiple of 14 that is less than 280.

This would also work:
$$floor(\frac{380 - 250}{14}) + 1$$

7. Aug 13, 2010

### Helicobacter

Re: Divisibility

Thanks

Can you tell me whether your formulas are generalizable and whether the divisor is always the LCM of the two given numbers?

8. Aug 13, 2010

### Staff: Mentor

Re: Divisibility

Probably. But brute force is superior to using a poorly-understood or incorrect formula that gives incorrect results.

This was a simple problem that took me all of a minute or two to list the numbers in the set, and count them. After I knew how many numbers there were I was able to come up with a formula that gave the same result.
That seems reasonable.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook