Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I generalized the sum of all numbers less than or equal to k that are multiples of $a, b, c, d,\ldots$ but I used the formula for the union of $n$ sets. Afterwards, soemone told me that I was "over-complicating it" because the generalization could easily be achieved using the least common multiple function. Here's my problem: I don't remember how I was told I could do it. I thought that they had told me to just subtract all the multiples of $\operatorname{lcm}(a, b, c,\ldots)$ like so:

$$\sum_{i=1}^{\lfloor k/a\rfloor}ai + \sum_{i=1}^{\lfloor k/b\rfloor}bi + \sum_{i=1}^{\lfloor k/c\rfloor}ci + \cdots-\sum_{i=1}^{\lfloor k/\operatorname{lcm}(a,b,c,\ldots)\rfloor}\operatorname{lcm}(a,b,c,\ldots)i$$

(the first three "sigmas" are the sum of all the numbers under k that are multiples of $a$, $b$ and $c$ disregarding non-unique multiples)

but then I realized that would be wrong, since there could be numbers that are multiples of $a$ and $b$ that are not multiples of $c$, which the least common multiple function could never account for. So, my question is, what might have they told me? I know for a fact that they mentioned $\operatorname{lcm}(x)$. What methods for generalizing this make us of the least common multiple function? Thank you.

share|improve this question
2  
Looks like a job for inclusion-exclusion to me. You have the terms that are divisible by a, b, ...; next you remove those that are divisible by ab, ac, ..., bc, bd, ...; then add back those that are divisible by the products of three terms; until you get to all. If the numbers are not relatively prime, it probably is trickier, but it is late and I am tired. –  marty cohen Aug 27 '11 at 4:50

1 Answer 1

up vote 2 down vote accepted

You would want to use the Principle of Inclusion-Exclusion. For two numbers (say $a$ and $b$), you find all the multiples of each number, but this double-counts for those numbers are multiples of both. So you subtract those. For three (say $a$, $b$, and $c$), you find all the multiples, but this double-counts numbers that are multiples of $ab$, $bc$, and $ac$. So you take those out. But then, we had originally triple-counted multiples of $abc$, and then we took them all out. So we add them back in.

So the general form would look something like

$$\sum_i^{\frac{k}{a}} ai +\sum_i^{\frac{k}{b}}bi + ... \left( \text{one element sums} \right) - \left( \sum_i^{\frac{k}{ \text{lcm}(a,b)}} \text{lcm}(a,b)i + \left( \text{two element sums} \right) \right) +$$ $$ \left( \sum_i^{\frac {k}{\text {lcm} (a,b,c)}} \text{lcm}(a,b,c)i + \text{three element sums} \right) - \left( \text{four element sums} \right) ... $$

And although it looks a bit scary, it's simple to execute in practice.

share|improve this answer
    
So are you telling me that my original approach wasn't "over-complicating it"? I was correct in trying to use the formula for the union of $n$ sets? –  Hautdesert Aug 27 '11 at 21:02
    
@Hautdesert I don't know what you mean for the formula for the union of n sets. I think this is a very simple method here. From your question, I got the impression that you had one addition and one subtraction, which is incorrect unless you do some very complicated work. –  mixedmath Aug 27 '11 at 23:18
    
Maybe I didn't convey my ideas well enough, but I was saying that someone else had suggested that method to me, but it is obviously wrong. I was looking for a method that didn't use the inclusion-exclusion principle to generalize this problem, but I have realized now that any method which satisfies this condition would probably have been too complicated for a problem so simple. –  Hautdesert Aug 28 '11 at 5:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.