##
Project-Euler
/
**1**

Problem 1 asks:

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

Very simple, just go through every number between 0 and 1000, and if it’s a multiple of 3 or 5 add it to the running total.

Here’s my initial solution in Java:

public class Problem1 { public static void main(String[] args) { int sum = 0; for (int i = 0; i < 1000; i++) { if (i % 3 == 0 || i % 5 == 0) sum += i; } System.out.println(sum); } }

This is fine if you only want to find the multiples below 1000, but for big ranges we can do *far* better.

We can solve this problem in constant time by making use of the fact that: $$\sum_{i=1}^ni = \frac{n(n+1)}2$$

The sum of all multiples of 3 and 5 below n can be calculated as: $$3\sum_{i=1}^{\lfloor\tfrac{1}{3}n-1\rfloor}i + 5\sum_{i=1}^{\lfloor\tfrac{1}{5}n-1\rfloor}i - 15\sum_{i=1}^{\lfloor\tfrac{1}{15}n-1\rfloor}i$$

Multiples of 15 have to be subtracted to remove duplicates which were multiples of both 5 and 3. One needs to be subtracted from each range because the questions says *below* 1000.

Using the earlier formula, this expands to: $$\frac{3\lfloor\tfrac{1}{3}m\rfloor(\lfloor\tfrac{1}{3}m\rfloor+1) + 5\lfloor\tfrac{1}{5}m\rfloor(\lfloor\tfrac{1}{5}m\rfloor+1) - 15\lfloor\tfrac{1}{15}m\rfloor(\lfloor\tfrac{1}{15}m\rfloor+1)}2$$ where \(m = n -1\).

Translating into Java we get:

public class Problem1 { public static void main(String[] args) { final long RANGE = 1000; long m = RANGE - 1; long sum = (3 * (m / 3) * (m / 3 + 1) + 5 * (m / 5) * (m / 5 + 1) - 15 * (m / 15) * (m / 15 + 1)) / 2; System.out.println(sum); } }