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

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");

}


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

-
Does this produce the correct? My assumption is that you're probably off by 285 or 570. – nhgrif Aug 10 '14 at 13:14
got the answer as correct. otherwise I would not post it here. – JaDogg Aug 10 '14 at 13:18
Oh, I see the last one subtracts. – nhgrif Aug 10 '14 at 13:22
How has noone picked up on void main(void)?! Needs to return int type, and either don't specify parameters, or (int argc, char *argv[]) – Ollie Ford Aug 10 '14 at 22:00
@OllieFord : If you can please post an answer, If you think it has potential value to the community. IMHO it does and you should post an answer – JaDogg Aug 10 '14 at 22:09

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");

return 0;

}


I put the above together in a working Ideone

-
If you omit the 0th term as the problem does, you can also eliminate the $+1$ when calculating $n$ and use the more standard formula for summing the first $n$ positive integers: $n (n + 1) \over 2$. – David Harkness Aug 10 '14 at 19:46
Your sum_of_series function might still be incomplete without a better explanation of the formula or a URL to an explanation of the formula. I know at this point it's in a form that will be more familiar to mathematicians, and the formulas you included look familiar to me from Calculus. The average programmer is not a mathematician however and probably unfamiliar with this formula. Meanwhile, the problem statement is pretty easy to understand for non-mathematicians. When the code is harder to understand then the problem statement, you need really, really good comments. – nhgrif Aug 10 '14 at 20:47
Should probably mention that void main(void) is a non-standard signature for C (and C++) since this is code review. – Rapptz Aug 11 '14 at 0:17
The average programmer is not a mathematician however how sad. – Cthulhu Aug 11 '14 at 6:17
@Cthulhu The average programmer cannot be above average at everything. I'm a programmer and a mathematician, perhaps it is sad that I'm not a designer, statistician, or system engineer. Or perhaps not. Regardless of how we react emotionally to it, there are many talented engineers that don't have mathematics as one of their strong suits, and I have enjoyed working with some of these. – Eric Wilson Aug 11 '14 at 18:31

## 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 positionnumber_of_terms, differencestep, and maybe also sum_of_seriessum_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);
}

-
count_multiples_under is a much better name. all in all, this is much more readable. – njzk2 Aug 11 '14 at 19:38

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]);
// ...
}


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
$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
$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
\$ gcc t.cpp  && ./a.out 10000000
sum of all the multiples of 3 or 5 below 10000000


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.)

-
About the formula 23{n}16{m}8 its a little bit lengthy but it is not difficult to prove that there is a pattern like that. Eventually you can ask on math.stackexchange.com – Emanuele Paolini Aug 10 '14 at 21:09

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)$.

-
Is this supposed to be a serious answer? Nonetheless, it's just a code dump and not an actual review. – Jamal Aug 10 '14 at 19:59
It looks a bit better now... but this solution is actually $O(n)$. It's very similar to a now-deleted answer that received the same criticism. – Jamal Aug 10 '14 at 20:11
It means linear complexity. This code loops through a certain number. Constant complexity would involve single operations. The OP's code is $O(1)$. – Jamal Aug 10 '14 at 20:16
@EmanuelePaolini - you're right, since the input is a constant, all Solutions will be O(1), and there is no concept of scaling at all. Talking time-complexity for scaling is... going to require assumptions. Still, your solution is about 1000 times slower than the OP's – rolfl Aug 10 '14 at 20:31
Project Euler is way more than the right solution. Also, do this, int n = whateverNumber; for (int i = 1; i < n; i++) Can you see the O(n) now? – Silviu Burcea Aug 11 '14 at 7:16