# Project Euler

Type of site Problem Solving Website Colin Hughes projecteuler.net 31,756 (Jul 2017)[1] No Free October 5, 2001

Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs.[2][3] The project attracts adults and students interested in mathematics and computer programming. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide.[4] It includes over 600 problems,[5] with a new one added once every two weeks. Problems are of varying difficulty but each is solvable in less than a minute of CPU time using an efficient algorithm on a modestly powered computer. As of May 2018 Project Euler has about 800,000[6] users, from all over the world, who have solved at least one problem.[7]

## Features of the site

A forum specific to each question may be viewed after the user has correctly answered the given question.[8] Problems can be sorted on ID, number solved and difficulty. Participants can track their progress through achievement levels based on the number of problems solved. A new level is reached for every 25 problems solved. Special awards exist for solving special combinations of problems, for instance there is an award for solving fifty prime numbered problems. A special "Eulerians" level exists to track achievement based on the fastest fifty solvers of recent problems so that newer members can compete without solving older problems.[9]

## Example problem and solutions

The first Project Euler problem is

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.

Though this problem is much simpler than the typical problem, it serves to illustrate the potential difference that an efficient algorithm makes. The brute-force algorithm examines every natural number less than 1000 and keeps a running sum of those meeting the criteria. This method is simple to implement, as shown by the following pseudocode:

Set TOTAL to 0;
for NUM from 1 through 999 do
if NUM mod 3 = 0 or if NUM mod 5 = 0 then
output TOTAL


For harder problems, it becomes increasingly important to find an efficient algorithm. For this problem, we can reduce 1000 operations to a few by using the inclusion–exclusion principle and a closed-form summation formula.

{\displaystyle {\begin{aligned}\mathrm {sum} _{\text{3 or 5}}(n)&=\mathrm {sum} _{3}(n)+\mathrm {sum} _{5}(n)-\mathrm {sum} _{15}(n)\\\mathrm {sum} _{k}(n)&=\sum _{i=1}^{\left\lfloor {\frac {n-1}{k}}\right\rfloor }ki\\\sum _{i=1}^{p}ki&=k{\frac {(p+1)p}{2}}\end{aligned}}}

Here, ${\displaystyle \mathrm {sum} _{k}(n)}$ denotes the sum of multiples of ${\displaystyle k}$ below ${\displaystyle n}$. In big O notation, the brute-force algorithm is O(n) and the efficient algorithm is O(1) (assuming constant time arithmetic operations).