Archive for January, 2013

Project Euler with Julia

January 4, 2013 Leave a comment

Disclaimer: Project Euler discourages the posting of solutions to their problems, to avoid spoilers. The three solutions I have presented in my blog are to the three first problems (the easiest and most popular), as a means to advertise and encourage my readers to “push the envelope” and go beyond brute-force solutions.

Just for fun, and as a means to learn Julia, I will be attempting problems from the Project Euler coding exclusively in that promising computer language.

The first problem is very simple:

Multiples of 3 and 5
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 multip les is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

One easy-to-code way is by dealing with arrays:

julia> sum( filter( x->((x%3==0) | (x%5==0)), [1:999] ) )

A much better way is to obtain it via summation formulas: Note that the sum of all multiples of three between one and 999 is given by

3+6+\dotsb+999 = 3 (1+2+\dotsb+333) = 3 \frac{333\cdot 334}{2} = 166833.

Similarly, the sum of all multiples of five between one and 995 is given by

5+10+\dotsb+995 = 5 (1+2+\dotsb+199) = 5 \frac{199\cdot 200}{2} = 99500.

Finally, we need to subtract the sum of the multiples of both three and five, since they have been counted twice. This sum is

15+30+\dotsb+990 = 15 (1+2+\dotsb+66)= 15 \frac{66\cdot 67}{2}= 33165.

The final sum is then, 166833+99500-33165=233168.

%d bloggers like this: