re: Project Euler #1 - Multiples of 3 and 5 VIEW POST

FULL DISCUSSION
 

I'll take a mathematical approach.

The sum of the first n positive integers is n*(n + 1)/2. Multiply by k, and you get the sum of the first n multiples of k.

There are 333 multiples of 3 below 1000, and 199 multiples of 5, so we get 166833 and 99500, respectively. But we can't just sum them, as we'd count the multiples of 15 twice (15 is their least common multiple), so we have to subtract those once (total: 33165).

Result: 233168

In general, let's use JavaScript for example:

const limit = 1000;
const m = 3, n = 5;

const mulM = Math.floor((limit - 1) / m);
const mulN = Math.floor((limit - 1) / n);

const lcm = leastCommonMultiple(m, n);
const mulLcm = Math.floor((limit - 1) / lcm);

const result = m * mulM * (mulM + 1) / 2
  + n * mulN * (mulN + 1) / 2
  - lcm * mulLcm * (mulLcm + 1) / 2;

There, no iterations, pure math 👍 And blazing fast

Using JavaScript's new support of BigInt, it's immediate even with huge numbers like 123456789012345678901234567890: it's 3556368375755728575115582031196717989244271707186887161545.

 
 

yesss the Gaussian sum is such a good tool!

code of conduct - report abuse