## Just another counting problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

There are $n_3 = 1000/3 = 333$ multiples of $3$ and $n_5 = 1000/5 - 1 = 199$ multiples of $5$. Some of those numbers are multiple of both $3$ and $5$ (i.e. they are multiples of $15$). When summing, we need to avoid summing twice we need to subtract those numbers.

There are $n_{15} = 1000/15 = 66$ multiples of $5$. The result is:

$3 \cdot \frac{n_3(n_3+1)}{2}+5 \cdot \frac{n_5(n_5+1)}{2}-15 \cdot \frac{n_{15}(n_{15}+1)}{2}=233168$

This is a simple C++ program that verifies the math:

int main()
{
int n = 1000;
int sum = 0;
for ( int i = 1; i < n; i++ )
{
if ( ( i % 3 == 0 ) || (i % 5 == 0 ) )
{
sum += i;
}
}
int div3 = ( n – 1 ) / 3;
int div5  = ( n – 1 ) / 5;
int div15 =  ( n – 1 ) / 15;
int sumDirect =  3 * div3 * ( div3 + 1 ) / 2 +
5 * div5 * ( div5 + 1 ) / 2  – 15 * div15 * ( div15 + 1 ) / 2;
if ( sum != sumDirect )
{
cout<<“Bad idea!”;
}
else
{
cout<<“Excellent!”;
}
}
Advertisements
This entry was posted in Algorithms, Math. Bookmark the permalink.