so, i've discovered projecteuler.net. however, i'm stuck on the first problem.

now, it isn't the actual solving of the problem itself, i already have my algorithm to solve it, however, i think there is a problem in my algorithms logic.

the question is as follows:

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.

[/quote]

and my c++ program to solve it is:


#include <iostream>
#include <math.h>

using namespace std;

int main()
{
int answer = 0;

for (int number = 0; number < 1000; number++)
{
if ((number%3) || (number%5) == 0)
{
if ((number%3) && (number%5) == 0)
{
answer += 0;
}
else
{
answer += number;
}
}
}

cout << answer <<endl;
return 0;
}

when i change the run until clause in the for statement to 10 so i can check my working out against the correct solution however, it outputs 22 instead of 23, and i just can't figure out why this is.

any help at all would be much appreciated as i've looked at this problem from every which way and cannot see the error.

Hi there,

in the initial if-statement, you're missing a '== 0'. This way the left hand side of the condition if ((number%3) || (number%5) == 0) checks out wrong.

Warning! Spoilers and totally unproven claims ahead

Also, I think you can compute the numbers directly without a loop if you use the fact that the sum of the numbers {1, ..., n} equals to n*(n-1). Let f_n({a}) be the sum of the numbers from 1..n which are multiples of a: . The <...> thing is meant to be 1 if the inside statement is true, 0 otherwise (basically the same as in your algorithm's inner-most if-statement). However, you can factor out the a: . Now, if your interested in multiples of {a,b} instead of just {a}, you can apply the principle of inclusion-exclusion: Just using will count multiples of both a and b twice, right? So you have to subtract these again: . Here, the 'gcd(...)' means the greatest common divisor. You might want to use it as any number is divisible by both a and b if and only if it is divisible by gcd(a,b).


- Michael

The problem is indeed the lack of comparison against zero.

[quote name='Michael N.' timestamp='1307253228' post='4819645']
You might want to use it as any number is divisible by both a and b if and only if it is divisible by gcd(a,b).

Except that the problem is the sum of numbers divisible by a or b, not a and b.

Logically the for-loop should start at 1, not 0, and the innermost if-statement is not needed, because you don't care if it is a multiple of both since you still do the same thing.
No need to add zero to 'answer' either.
[/quote]

the innermost if was kind of my attempt at doing an exclusive or statement, i think i can condense it into one if statement.

thank you, i didn't include the other check if it is equal to 0 because i didn't realize it was necessary. obviously i was mistaken.

re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

Multiples of both 3 and 5 won't be counted twice. You only loop through each number once, and your logic does not allow for it to be counted twice in one loop iteration.

I think you should loop through multiples of 5 and add if below 1000 and then rhe same with multiples of 3 UNLESS its dividable by 5 in wich case you have already added it

you could, and that is a perfectly valid solution, however, in terms of optimising the program, this would not be advised.

[quote name='Shruubi' timestamp='1307270515' post='4819699']
re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

Multiples of both 3 and 5 won't be counted twice. You only loop through each number once, and your logic does not allow for it to be counted twice in one loop iteration.
[/quote]

thank you for that clarification, i think i put my mind in a state where i was looking for a more complex solution than was needed.

Except that the problem is the sum of numbers divisible by a or b, not a and b.

True, but the subtraction involving the gcd is only there as my method counts multiples of 'a' and 'b' independently. Therefore, something like 15 would be counted twice when adding up all the multiples of 3 or 5. I see nothing wrong with that...

Very simple example: Add up all the numbers from 1 to N which are multiples of 3 or multiples of 3. Then you immediately see why you need the subtraction in . Since gcd(3,3)=3 this quickly simplifies to f_n({3,3})=f_n({3}). In general, however, this overcounting has to be handled (Although, as it was pointed out, the OP's algorithm doesn't do this).

- Michael.