Some time ago I came across Project Euler, which hosts a collection of mathematical problems which are primarily designed to be solved by computer programming. From the web site:
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
As at today there are 299 problems on the site, and I thought it might be an interesting task to try and solve some of them, outlining my reasoning as we progressed through them. I will be using Delphi 2007 (Pascal) to work through them but hopefully the code should be easy to convert to other languages.
Problem 1 is stated 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.
My initial thought was to find the sum of all the multiples of 3 using the formula for the sum of an arithmetic progression, and then adding the sum of all multiples of 5.
This however would give us the wrong result as there are some numbers within the range 1 to 999 which are multiples of both 3 and 5 and we would have counted them twice. We could get around this by subtracting the sum of all mutiples of 15 (3 times 5) from the final result, but this would be three calculations or steps in the program.
I was looking for a more elegant solution (bearing in mind that I was using a computer program and the time taken to loop from 1 to 999 would be negligible).
This is the final code that I came up with:
procedure TfrmMain.Problem1; var i, numTotal: integer; begin numTotal := 0; for i := 1 to 999 do if (i mod 3 = 0) or (i mod 5 = 0) then inc(numTotal, i); ShowMessage(IntToStr(numTotal)); end;
Line 6 initialises the result(numTotal) to 0.
Line 7 runs the loop from 1 to 999 executing the statement in line 8. This uses the mod function to check whether the current number is divisible by 3 or 5; if it is it is added to the running total.
Finally, the IntToStr function converts the result numTotal to a string, and the ShowMessage displays the resulting string.
On my PC the result is displayed virtually instantaneously.
Tags: Mathematics, Project Euler