/sci/ - Science & Math

[Anonymous No.5358570]

>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.

Simple code, with a O(n) brute force algorithm. Does anyone know the O(1) algorithm?

[Anonymous No.5358585]

As an aspie who has solved well over a hundred problems on Project Euler, I'm telling you to do your own thinking.

[Anonymous No.5359087]

The multiples of 3 form an arithmetic series, the sum of which can be calculated in O(1) time.
The multiples of 5 form an arithmetic series, the sum of which can be calculated in O(1) time.
The multiples of 15 form an arithmetic series, the sum of which can be calculated in O(1) time.
Note that a number is a multiple of 15 iff it is a multiple of both 3 and 5, so the multiples of 15 will have been included in both the previous series.

[mathfag No.5360938]

<span class="math">
\frac{\frac{1}{3}(\frac{1}{3}+1)+\frac{1}{5}(\frac{1}{5}+1)-\frac{1}{15}(\frac{1}{15}+1)}{2}1000^{2}
[/spoiler]