2
$\begingroup$

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.

  • 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.2011-08-27

1 Answers 1

2

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.

  • 0
    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.2011-08-28