Multiples of 3 and 5
This is the first post of a series entitled Project Euler In Under 0.1ms
Project Euler #1
If we list all the natural numbers below
10
that are multiples of3
or5
, we get3
,5
,6
and9
. The sum of these multiples is23
.Find the sum of all the multiples of
3
or5
below1000
.
Common (and slow) solution
The most common, naive solution involves a simple loop from 0
to x
, checking
whether n
is multiple of 3
or 5
and then adding n
to the sum. Pretty
straightforward:


Stay put as a Pythonista
Things get worse if we’re not true Pythonistas and dare to use
filter
. It takes
almost twice the time to complete compared to the previous one:


A slightly better approach
Instead of looping up to x
, we could loop until the maximum multiple of 3
or
5
that is less than x
. As we want the maximum one, it should be multiple of
3
, since 3 < 5
. Just remember not to readd “duplicate numbers”, those
that are multiples of both 3
and 5
:


A better approach
But, wait! We could just loop from 0
to x
, 3
by 3
, summing all values,
then do the same 5
by 5
– but not readding dupes:


Same approach improved a bit
We’re good readding duplicate numbers as long as we subtract them later:


Same approach improved some more
We can gain some precious milliseconds benefitting from Python’s fast addition. The following is around three times faster than the previous one:


WOW! From 497.477ms
down to 38.212ms
! But even so, this is far from being
fast. We’ve just saved hundreds of milliseconds. We need a completely different
approach.
Going under 0.1ms
Look at what we’ve got so far. Each of those sums is the sum of a series! And, as young Gauss brilliantly found out, we can write them as mathematical equations. Kudos, Johann Carl Friedrich Gauss.
Take S
, for instance, the sum of all natural numbers from 1
to n
. We can
define it as:
Analogously, we can state the following:
Considering the above, to sum all natural numbers below 25
that are multiples
of 5
, we could just sum all of them up to 20
, the 4th
element (i.e.
floor((25  1) / 5) = 4
). Thus, defining x' = x  1
, we can use the
following to obtain the sum of all multiples of 5
below x
:
Then we can take:
Replace it into equation 3 to end up with:
And solve the problem really fast:


About the author
Pablo Aguiar is a software engineer and coffee geek from Brazil. He's curious about computers, maths and science. He enjoys a good coffee and loves literature. Read more...