Project Euler: Coding to Solve Maths Problems

Project Euler, named after one of the greatest mathematicians of all time, has been designed to bring together the twin disciplines of mathematics and coding.  Computers are now become ever more integral in the field of mathematics – and now creative coding can be a method of solving mathematics problems just as much as creative mathematics has always been.

The first problem on the Project Euler Page is as follows:

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.

This is a reasonably straight forward maths problem which we can solve using the summation of arithmetic sequences (I’ll solve it below!) but more interestingly is how a computer code can be written to solve this same problem.  Given that I am something of a coding novice, I went to the Project Nayuki website which has an archive of solutions.  Here is a slightly modified version of the solution given on Project Nayki, designed to run in JAVA:

 

The original file can be copied from here, I then pasted this into an online JAVA site jdoodle. The only modification necessary was to replace:

public final class p001 implements EulerSolution with public class p001

Then after hitting execute you get the following result:

i.e the solution is returned as 233,168. Amazing!

But before we get carried away, let’s check the answer using some more old fashioned maths. We can break down the question into simply trying to find the sum of multiples of 3 under 1000, the sum of the multiples of 5 under 1000 and then subtracting the multiples of 15 under 1000 (as these will have been double counted). i.e:

(3 + 6 + 9 + … 999)  +  (5 + 10 + 15 + … 995)  – (15 + 30 + 45 + …990)

This gives:

S_333 = 333/2 (2(3)+ 332(3)) = 166,833
+
S_199 = 199/2 (2(5) + 198(5)) = 99, 500
–
S_66 = 66/2 (2(15) +65(15) = 33, 165.

166,833 + 99, 500 – 33, 165 = 233, 168 as required.

Now that we have seen that this works we can modify the original code.  For example if we replace:

if (i % 3 == 0 || i % 3 == 0)
with
if (i % 5 == 0 || i % 7 == 0)

This will find the sum of all the multiples of 5 or 7 below 1000.  Which returns the answer 156,361.

Replacing the same line with:

if (i % 5 == 0 || i % 7 == 0 || i % 3 == 0)

will find the sum of all the multiples of 3 or 5 or 7 below 1000, which returns the answer 271,066.  To find this using the previous method we would have to do:

Sum of 3s + Sum of 5s – Sum of 15s + Sum of 7s – Sum of 21s – Sum 35s – Sum of 105s. Which starts to show why using a computer makes life easier.

This would be a nice addition to any investigation on Number Theory – or indeed a good project for anyone interested in Computer Science as a possible future career.