Project Euler #1 in Java - Why result correct although rounded down?

Question

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

I am having problems with understanding why the solution below still returns the correct result because x3, x5 and x15 use int after division. That means that the result of the division is always rounded down and the decimals are neglected.

When I tried to replace all 3 ints by doubles I got the wrong result.

The solution is based on the following observation:

1 + 2 + ... + n = n*(n+1)/2

public static void main(String[] args) {
    int nr = 1000;
    nr--;
    int x3 = nr/3;
    int x5 = nr/5;
    int x15 = nr/15;

    long sum1 = 3*x3*(x3+1); 
    long sum2 = 5*x5*(x5+1);
    long sum3 = 15*x15*(x15+1);

    long sum = (sum1+sum2-sum3)/2;
    System.out.println(sum)
}

Reference

Answer 1

When I tried to replace all 3 ints by doubles I got the wrong result.

You need to do the flooring from integer division because there aren't a fractional number of numbers divisible by the divisor: there aren't 199.8 positive numbers less than 1000 divisible by 5, there are 199.

So, by using double, you're overcounting the total:

sum2 = floor(5 * 199.8 * 200.8) = floor(200599.2) = 200599
  vs
sum2 = floor(5 * 199   * 200  ) = floor(199000  ) = 199000

Answer 2

Taking 3 as an example, the sum of numbers that are divisible by 3 and are less than 1000 is: (3 + 6 + 9 + 12 + ... + 999)

The above can be rewritten as 3 * (1 + 2 + 3 + .... + 333). And 333 = integer part of (999/3). It can also be written as floor(999/3).

The sum (1 + 2 + 3 + .... + 333) = 333 * (333 + 1) / 2 or floor(999/3) * (floor(999/3) + 1) / 2 = 55611. This is exactly what is done by the code above. Using int gives you an easy way of doing the floor operation.

If you used double, you would do 333.333 * (333.333 + 1) / 2 which is 55722.111, a number different from 55611. That brings in the discrepancy that you see.

Answer 3

The integers x3, x5, and x15 are simply answers to the question, "How many positive integers less than M are multiples of N?" Here is a table that demonstrates this when N = 3:

M Count
1 0
2 0
3 0
4 1
5 1
6 1
7 2
...

As you can see, the generalization of the answer is Count = floor((M - 1) / N), which happens to be how positive integer division is defined in Java.

I inferred that this rounding is what you were asking about, given this is the only truncating integer division from the code above.