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.

Source: http://projecteuler.net/problem=1

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s