Project Euler #1 Sum of all the multiples of 3 or 5 below 1000

Question

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.

My solution:

#include <stdio.h>
#define TOP_LIMIT 1000

float sum_of_series(float start_from,float position,float difference)
{
    return (position/2) * 
        ( 2 * start_from + (position-1) * difference);
}

int find_last_multiple(int limit,int multiplier){
    return limit - (limit % multiplier);
}

void main(void){

    float last_position_3 = 
        find_last_multiple( TOP_LIMIT-1 , 3 ) / 3;

    float last_position_5 = 
        find_last_multiple( TOP_LIMIT-1 , 5 ) / 5;

    float last_position_15 = 
        find_last_multiple( TOP_LIMIT-1 , 15 ) / 15;

    float sum_of_series_3 = sum_of_series(3,last_position_3,3);
    float sum_of_series_5 = sum_of_series(5,last_position_5,5);
    float sum_of_series_15 = sum_of_series(15,last_position_15,15);

    float answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;    

    printf("sum of all the multiples of 3 or 5 below 1000\n");
    printf("answer = %f\n",answer);

}

I compiled it with: gcc (GCC) 4.8.3 20140624 (Red Hat 4.8.3-1)

Answer 1

In general, your algorithm/solution is clever. It is an \$O(1)\$ solution which I like, when most other solutions would be an \$O(n)\$ and do a modulo on 3 and 5. The trick for subtracting the double-count is something that should have a clear comment, including the reason why.

The find_last_multiple is also a neat solution. No issues with that, and it is simple enough to not require a comment.

Unfortunately the sum_of_series has some problems.... it should be commented, for a start... the logic is far from obvious.... I have not figured it out... yet.

Also, at this point it becomes float based calculations, and that threw me for a second. I immediately started thinking int-based math because the code has int constants, and it does int values in the find_last_multiple but it then does implicit casts to float. Very confusing.

Finally, it makes the assumption that that the series starts from 3, 5, or 15, but the question description starts from somewhere else.... I suggest you discard the starts_from parameter, and simply use the difference instead.

So, using float-based logic, and returning a float based solution is unexpected.... and I would expect there to be some comment as to why the sum of integers in a series is a float.

Finally, your sum_of_series should represent the standard formula for the sum-of-a-series (see the alternate form in wikipedia):

$$ \frac{n}{2}(2a + (n - 1)d) $$

where n is the number of terms in the series, a is the start value, and d is the difference.

That can be simplified by setting a to be 0 (eliminating the 2a term), and for int math by doing:

$$ \frac{n(n - 1)}{2}d $$

Mathematically, any multiple of an even number is always going to be even. Now, either \$n\$ or \$n - 1\$ is even.... so, \$n(n-1)\$ will be even, and safe to divide by 2.

I would also start from 0. Using integer math, the problem is simpler:

int sum_of_series(int limit, int difference)
{
    // from: http://en.wikipedia.org/wiki/Arithmetic_progression
    // formula for calculating the sum of a progression from 0 to a 'limit'
    // in steps of 'difference'. e.g. limit 10, difference 2 adds 0, 2, 4, 6, 8, 10 = 30
    int n = 1 + limit / difference; // integer math gives number of terms including term 0
    return ((n * (n - 1)) / 2) * difference;
}

So, you can use the above safely as:

int sum = sum_of_series(999, 15);

which will give the result 15 * (67 * 66) / 2 or 33165

Note that the problem statement requires the sum of values less than 1000, and the sum_of_series formula calculates inclusive of the limit, so we use the limit of 999, not 1000

Additionally, using the int-based logic, there is no need for there to be the find-limit method at all. This reduces your main method to:

int main(void){

    int sum_of_series_3 = sum_of_series(999,3);
    int sum_of_series_5 = sum_of_series(999,5);
    int sum_of_series_15 = sum_of_series(999,15);

    int answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;    

    printf("sum of all the multiples of 3 or 5 below 1000\n");
    printf("answer = %d\n",answer);

    return 0;

}

I put the above together in a working Ideone

Answer 2

What you did well

Using a formula to compute sums is efficient. Using the inclusion-exclusion principle is smart. You chose descriptive names for your functions and variables. The intention is fully clear just from reading this single line:

float answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;

Concerns

The foray into floating-point is mildly disconcerting, for accuracy and performance reasons. I say "mildly", since I doubt that it has any real consequences in this particular solution, but I would still consider it bad practice to do integer calculations using floating point.

Mathematical expressions

You defined TOP_LIMIT as 1000, yet hard-coded 1000 in the format string. The output will look wrong if you ever need to change TOP_LIMIT.

sum_of_series(start_from, position, difference) could be clearer, by renaming position → number_of_terms, difference → step, and maybe also sum_of_series → sum_of_arithmetic_seq.

A possible simplification is to define more primitive, generically useful functions.

$$\begin{align*} \underbrace{3 + 6 + 9 + 12 + \ldots + 999}_{n\ \textrm{terms}}\ &= 3\ (1 + 2 + 3 + 4 + \ldots + n)\\ &= 3 \frac{n\ (n + 1)}{2} \end{align*}$$

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

int count_multiples_under(int limit, int step) {
    /* Integer division automatically rounds down as necessary */
    return (limit - 1) / step;
}

int main(void) {
    int limit = 1000;
    int sum_of_series_3  =  3 * sum_of_1_to_n(count_multiples_under(limit, 3));
    int sum_of_series_5  =  5 * sum_of_1_to_n(count_multiples_under(limit, 5));
    int sum_of_series_15 = 15 * sum_of_1_to_n(count_multiples_under(limit, 15));

    int answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;
    printf("sum of all the multiples of 3 or 5 below %d = %d\n", limit, answer);
}

Answer 3

As @rolfl pointed out, after you rewrite sum_of_series to work with integers and return an int, you could replace all float variables with int in the entire program. (And of course, change the last printf to use %d instead of %f.)

---

GCC gives me an error for void main, it wants it to return int.

---

It's good to avoid #define when possible. It would be better to use a global constant instead, or even a local constant in the main method. But the program becomes kinda fun if you make this a command line argument, for example:

#include <stdlib.h>

int main(int argc, char ** argv) {
    int top_limit = atoi(argv[1]);
    // ...
    printf("answer = %d\n", answer);
}

And then when you run it:

$ gcc t.cpp  && ./a.out 10
sum of all the multiples of 3 or 5 below 10
answer = 23
$ gcc t.cpp  && ./a.out 100
sum of all the multiples of 3 or 5 below 100
answer = 2318
$ gcc t.cpp  && ./a.out 1000
sum of all the multiples of 3 or 5 below 1000
answer = 233168
$ gcc t.cpp  && ./a.out 10000
sum of all the multiples of 3 or 5 below 10000
answer = 23331668
$ gcc t.cpp  && ./a.out 100000
sum of all the multiples of 3 or 5 below 100000
answer = 2333316668
$ gcc t.cpp  && ./a.out 1000000
sum of all the multiples of 3 or 5 below 1000000
answer = 233333166668
$ gcc t.cpp  && ./a.out 10000000
sum of all the multiples of 3 or 5 below 10000000
answer = 23333331666668

What the hell, the answer for powers of 10s (beyond 100) seems to always match the regex 23{n}16{m}8 where m = n - 1! How cool is that?

(For the larger numbers I had to change some of the int types to long.)

Answer 4

Why a so complicated algorithm when you can keep it as simple as:

#include <stdio.h>

int main() {
  int sum=0;                                                                                                                                  
  for (int i=1;i<1000;i++) {                                                                                                                  
    if (i % 3 == 0 || i % 5 == 0)                                                                                                             
      sum += i;                                                                                                                               
  }                                                                                                                                           
  printf("%d\n",sum); // 233168                                                                                                               
}

Since you have no input every solution is \$O(1)\$.