sum multiples in a given range

Question

well I want to sum up the multiples of 3 and 5. Not too hard if I want just the sum upon to a given number, e.g. -> up to 60 the sum is 870.

But what if I want just the first 15 multiples?

well one way is

void summation (const unsigned long number_n, unsigned long &summe,unsigned int &counter );
void summation (const unsigned long number_n, unsigned long &summe,unsigned int &counter )
{

       unsigned int howoften = 0;
       summe = 0;
       for( unsigned long i = 1; i <=number_n; i++ )
           if (howoften <= counter-1)
           {
               if( !( i % 3 ) || !( i % 5 ) )
               {
                   summe += i;
                   howoften++;
               }
           }
       counter = howoften;



   return;
}

But as expected the runtime is not accceptable for a counter like 1.500.000 :-/

Hm I tried a lot of things but I cannot find a solution by my own.

I also tried a faster summation algorithm like (dont care bout overflow at this point):

int sum(int N);
int sum(int N)
{
    int S1, S2, S3;

    S1 = ((N / 3)) * (2 * 3 + (N / 3 - 1) * 3) / 2;
    S2 = ((N / 5)) * (2 * 5 + (N / 5 - 1) * 5) / 2;
    S3 = ((N / 15)) *(2 * 15 + (N / 15 - 1) * 15) / 2;

    return S1 + S2 - S3;
}

or even

unsigned long sum1000 (unsigned long target);
unsigned long sum1000 (unsigned long target)
{
   unsigned int summe = 0;
   for (unsigned long i = 0; i<=target; i+=3) summe+=i;
   for (unsigned long i = 0; i<=target; i+=5) summe+=i;
   for (unsigned long i = 0; i<=target; i+=15) summe-=i;
return summe;

}

But I'm not smart enough to set up an algorithm which is fast enough (I say 5-10 sec. are ok)

The whole sum of the multiples is not my problem, the first N multiples are :)

Thanks for reading, and if u have any ideas, it would be great

Answer 1

Some prerequisites:

(dont care bout overflow at this point)

Ok, so lets ignore that completely.

Next, the sum of all numbers from 1 till n can be calculated from (see eg here):

int sum(int n) {
    return  (n * (n+1)) / 2;
}

Note that n*(n+1) is an even number for any n, so using integer artihmetics for /2 is not an issue.

How does this help to get sum of numbers divisible by 3? Lets start with even numbers (divisble by 2). We write out the long form of the sum above:

1 + 2 + 3 + 4 + ... + n

multiply each term by 2:

2 + 4 + 6 + 8 + ... + 2*n

now I hope you see that this sum contains all numbers that are divisible by 2 up to 2*n. Those numbers are the first n numbers that are divisble by 2.

Hence, the sum of the fist n numbers that are divisble by 2 is 2 * sum(n). We can generalize that to write a function that returns the sum of the first n numbers that are divisble by m:

int sum_div_m( int n, int m) {
    return sum(n) * m;
}

First I want to reproduce your inital example "up to 60 the sum is 870". For that we consider that

• 60/3 == 20 -> there are 20 numbers divisble by 3 and we get their sum from sum_div_m(20,3)
• 60/5 == 12 -> there are 12 numbers divisible by 5 and we get their sum from sum_div_m(12,5)
• we cannot simply add the above two results because then we would count some numbers double. Those numbers are those divisible by 3 and 5, ie divisible by 15
• 60/15 == 4 -> there are 4 numbers divisble by 3 and 5 and we get their sum from sum_div_m(4,15).

Putting it together, the sum of all numbers divisible by 3 or 5 up to 60 is

int x = sum_div_m( 20,3) + sum_div_m( 12,5) - sum_div_m( 4,15);

Finally, back to your actual question:

But what if I want just the first 15 multiples?

Above we saw that there are

n == x/3 + x/5 - x/15

numbers that are divisble by 3 or 5 in the range 0...x. All division are using integer arithmetics. We already had the example of 60 with 20+12-4 == 28 divisble numbers. Another example is x=10 where there are n = 3 + 2 - 0 = 5 numbers divisible by 3 or 5 (3,5,6,9,10). We have to be a bit careful with integer arithmetics, but no big deal:

    15*n == 5*x + 3*x - x
->  15*n == 7*x
->  x == 15*n/7 

Quick test: 15*28/7 == 60, looks correct.

Putting it all together the sum of the first n numbers divisible by 3 or 5 is

int sum_div_3_5(int n) {
    int x = (15*n)/7;
    return sum_div_m(x/3, 3) + sum_div_m(x/5, 5) - sum_div_m(x/15, 15);
}

To check that this is correct we can again try sum_div_3_5(28) to see that it returns 870 (because there are 28 numbers divisble by 3 or 5 up to 60 and that was the initial example).

PS Turned out that the question is really only about doing the maths. Though that isnt a big surprise. When you want to write efficient code you should primarily take care to use the right algorithm. Optimizations based on a given algorithm often are less effective than choosing a better algorithm. Once you chose an algorithm, often it does not pay off to try to be "clever" because compilers are much better at optimizing. For example this code:

int main(){
    int x = 0; 
    int n = 60;
    for (int i=0; i <= n; ++i) x += i;
    return x;
}

will be be optimized by most compilers to a simple return 1830; when optimizations are turned on because compilers do know how to add all numbers from 1 to n. See here.

Answer 2

You can do it in compile time recursively by using class templates/meta functions if your value is known in compile time. So there will be no runtime cost.

Ex:

template<int n>
struct Sum{
    static const int value = n + Sum<n-1>::value;
};

template<>
struct Sum<0>{
    static constexpr int value = 0;
};

int main()
{
    constexpr auto x = Sum<100>::value;
    // x is known (5050) in compile time
    return 0;
}