Project Euler : Problem 1 - Multiples of 3 and 5

Problem Statement : Multiples of 3 and 5

Problem 1 : 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$.

Concept and Theory

The concept is straight forward from Set Theory and Arithmetic Progression.

Venn_A_intersect_B

Lets say $A$ represents all the multiples of $3$ and $B$ represents all the multiples of $5$. But there are some numbers like $15$, $30$, $45$ which are multiple of both $3$ and $5$. We have to count them only once not twice.

$$A \cup B = A + B - A \cap B , \\ \text{where} \ A \ = \ All \ multiples \ of \ three \\ B \ = \ ALl \ multiples \ of \ five \\ A \cap B \ = \ All \ multiples \ of \ Fifteen$$

So all that is left is just one thing, how to get the sum of all these multiples.

The answer is counting how many terms are there which are less than the given limit. From there its simple, the quotient of $N/3$, $N/5$ and $N/15$ will give us the numbers of terms in the series of $3$, $5$ and $15$ receptively. Exclude the last number if it happens to be a multiple of $3$ or $5$ or $15$. Last term of the sequence can be calculated just by simply multiplying $3$, $5$ or $15$ with corresponding number of terms in sequence.

We knows that the sum of any given Arithmetic Progression can be given as,

$$sum = \frac{n}{2} (a_1 + a_n) \\ where \ n = \text{number of terms} \\ a_1 = \text{first term of the sequence} \\ a_n = \text{last term of the sequence}$$

That’s it. Just plug in the numbers and you will have your answer.

Before you code : Keep in mind we don’t have to consider the last number so always subtract $1$ from whatever is given limit.

Code

/**
 * A function that returns the sum of all the unique multiples of 3 and 5 below
 * given input n.
 *
 * Note : We have to exclude the n if its a multiple of 3 or 5
 *
 * @param n
 *            : input range
 * @return : the sum
 */
static public long sumOfMultiplesOf3And5(long n) {
  long res = 0;

  n = n - 1;

  long numberOfTermsThreeSeries = n / 3;
  long maxMultipleOfThree = (numberOfTermsThreeSeries) * 3;

  long numberOfTermsFiveSeries = n / 5;
  long maxMultipleOfFive = (numberOfTermsFiveSeries) * 5;

  long numberOfTermsFifteenSeries = n / 15;
  long maxMultipleOfFifteen = (numberOfTermsFifteenSeries) * 15;

  long sumOfMultipleOfThree = ((numberOfTermsThreeSeries * (3 + maxMultipleOfThree)) / 2);
  long sumOfMultipleOfFive = ((numberOfTermsFiveSeries * (5 + maxMultipleOfFive)) / 2);
  long sumOfMultipleOfFifteen = ((numberOfTermsFifteenSeries * (15 + maxMultipleOfFifteen)) / 2);

  res = sumOfMultipleOfThree + sumOfMultipleOfFive - sumOfMultipleOfFifteen;

  return res;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as above method $sumOfMultiplesOf3And5$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler
• Set Theory
• Arithmetic Progression