Project Euler -problem 1

Question

Find the sum of all the multiples of 3 or 5 below 1000.

https://projecteuler.net/problem=1 Is there any hack to do modulo operation in better way?

#include<iostream>

int main()
{
    unsigned int sum=0;

    for( int i = 0; i < 1000; ++i )
    {
        if( ( i % 3 == 0 ) || ( i % 5 == 0 )  ||
           ( ( i % 3 == 0 ) && ( i % 5 == 0 ) ) )
        {
            sum += i;  
        }
    }
    std::cout<< sum <<"\n";                         
}

Answer 1

This is not a hack.

if( ( i % 3 == 0 ) || ( i % 5 == 0 )  ||
   ( ( i % 3 == 0 ) && ( i % 5 == 0 ) ) )

What you have here is essentially:

if( a || b || ( a && b ) )

The truth table for a || b is:

\begin{array} {|cc|c|} \hline a & b & a \lor b \\ \hline 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ \hline \end{array}

Where \$0\$ indicates false and \$1\$ indicates true.

Therefore, the last part of your if is completely useless.

if( a || b || ( a && b ) )

is exactly the same as

if( a || b )

So your if statement can be:

if( ( i % 3 == 0 ) || ( i % 5 == 0 ) )

Arithmetic Sum

Project Euler 1 can be transformed into a Arithmetic sum problem.

Ask yourself these questions:

• How many numbers that are multiples by 3 are there below 1000 ?
• How many numbers that are multiples by 5 are there below 1000 ?
• How many numbers that are multiples by both 3 and 5 (i.e. 15) are there below 1000 ?

Then use the values for these individual arithmetic sums to arrive at your final answer. This will give your code a complexity of \$O(1)\$ instead of \$O(n)\$

As this is Project Euler, I only want to give you a little push in the right direction, hope this helps.

Answer 2

At first I apologize for bringing this off topic matter here. I heard of this website about one and a half year ago and I immediately fell in love with it. At first I tried to dive in with my programming knowledge and soon it drove me crazy as I failed in solving almost every problem except the simple arithmetic ones like the one mentioned here. The I finally figured out that these problems can't be solved with just developing algorithm without sufficient mathematical knowledge and of course without seeing the problem in a different angle. Let me explain.

Find the sum of all the multiples of 3 or 5 below 1000.

Of course we can use the modulo for each number below 1000 to determine which are divisible by 3 and 5. But isn't it a brute attack on these numbers? Why don't think it in a different way?

1. We need to get all the numbers below 1000 those are divisible by 3
2. We need to get all the numbers below 1000 those are divisible by 5
3. There will be repetition of numbers as there are a lot of numbers which are divisible by both 3 and 5.

In our high school there we must be taught something called Ven diagram. Honestly I didn't took it seriously. But later I found this ugly frightening figure has its own beauty and is very useful solving problems that are very complicated in first sight, like this problem.

You can see there are two circles A and B and they are overlapping with each other. In our problem we have two sets of numbers- those are divisible by 3 and those are divisible by 5. See these two sets have a common or intersecting set- those are divisible by both 3 and 5 (or 15 to be precise). Now the questing arises how would we get all those unique numbers from set A and B? Thats pretty simple as you might already understand. That is A union B, pretty simple, right? This expression takes care of all repetitive elements in those sets and produces a set with unique elements form both sets. Now how do we get A union B? The formula is-

A union B = A + B - A intersect B

That means we need to subtract the set of numbers those are divisible by both 3 and 5.

Lets find out which numbers belong to these sets- A, B and A intersect B

We have set our limit to 1000. Lets get the numbers those are divisible by 3 in the first place.

3, 6, 9, 12, 15, 18, 21, ..... 999

Lets take 3 common from them-

3( 1, 2, 3, 4, 5, 6, 7, ... 333 )

Can you see it? its just a simple linear arithmetic progression. Lets do the same for 5.

5, 10, 15, 20, 25, 30, 35, 40, ... 1000
5( 1, 2, 3, 4, 5, 6, 7, 8, ... 200 )

Again another linear arithmetic progression.

For 15 (divisible by both 3 and 5)

15, 30, 45, 60, 75, ... 990
15( 1, 2, 3, 4, 5, 6, ... 66 )

We need to take their summations- 1/2 * n(n+1) this is the formula for getting the some of a linear arithmetic progression, n is total number of elements in the series.

A = [ 1/2 * 333 * (333+1) ] * 3 = 166833
B = [ 1/2 * 200 * (200+1) ] * 5 = 100500
A intersect B = [ 1/2 * 66 * (66+1) ] * 15 = 33165

Finally,

A union B = A + B - A intersect B

    = 166833 + 100500 - 33165 = 234168

This would be the finishing of the discussing. But WAIT as I mentioned earlier I have solved this problem and that solution is not matched with this one!! WHY !!

Finally I figured I out, this is the result of not reading the question properly.

They asked for the number below 1000, but what I have done here? for 3 and 15 it was okay, but for 5? 1000 is divisible by 5! We can't include it in the set!!

So the actual summation would be 233168, 1000 less than what we got here.

People might argue why I have posted the whole solution here. But thing is that, anyone with a little knowledge of programming and the basic understanding of modulo can solve this problem like the questioner. Is this the right way of solving these problems? Was it the intention behind developing this problem bank? Of course not, at least I believe. They certainly want us to look at problems in a different angle. Look things those are hidden in the plain sight. Sketch the idea before painting actually.

This post is for future reference only, intended to them those are interested solving the problems in this website. But also for others to show there could be some other perspective to any problem.

Thanks for reading.

EDIT

As per suggestion by @200_success I am rewording here.

As per the original question I agree with @Simon André Forsberg there is certainly nothing wrong with the modulo operation. And also it can be broke down to a simpler version A || B as he already mentioned.

I want to add with it that the condition writing is very easy with the basic understanding of Digital Logic. I am just breaking down the idea.

In digital logic design || is represented as + and && is as * (and there are some more). So the condition becomes A + B + AB. Now you can have AB as many times as you like as its just an OR operation, so we can rewrite

A + B + AB 
= A + AB + B + AB
= A(1+B) + B(1+A)

If you OR anything with a true then the result will always be true. Here (1+B) = 1 and (1+A) = 1. So the expression will be A+B

Using this algorithm you are not actually checking the numbers which are divisible by both 3 and 5. Still it gets you the correct answer. The reason behind is you are just traversing throw the numbers and moving forward. There is no chance of any repetition here. The accepted answer is all good :)

Answer 3

I rewrote my code as follows:

#include <iostream>

int main()
{
    // 3 + 6 +....+999 = 3 ( 1 + 2+ ...+333) =3 * ( 333 * 334)
    unsigned int sum_mult_3_upto_1000  =  3 * 333 * 334 >> 1;
    unsigned int sum_mult_5_upto_1000  =  5 * 199 * 200 >> 1;
    unsigned int sum_mult_15_upto_1000 =  15 * 67 * 66  >> 1;

    unsigned sum = sum_mult_3_upto_1000 + 
                   sum_mult_5_upto_1000 - sum_mult_15_upto_1000;
    std::cout<< sum <<"\n";
}