Project Euler

Project Euler

Type of site	Series of computational mathematics problems
Created by	Colin Hughes
URL	projecteuler.net
Commercial	No
Registration	Free
Launched	5 October 2001

Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts graduates and students interested in mathematics and computer programming. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide. It includes 875 problems as of 6 February 2024, with a new one added approximately every week. 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.

Features of the site

A forum specific to each question may be viewed after the user has correctly answered the given question. 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.

Example problem and solutions

The first Project Euler problem is 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 multiples is 23.

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

This is the first problem in the site. It is a 5% rated problem, one of the easiest on the site. The initial approach the newbie solver can come up with is initially just bruteforce, as the upper bound, in our case, 1000 is rather small, and any home computer today can complete the task within seconds. A Python code that solves it is presented below.

def solve(limit):
    total = 0
    for i in range(limit):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total

print(solve(1000))

So we have an $O(n)$ solution. For those not familiar with the terminology, it means that the number of computations performed is expected to converge to some multiple of $n$. Let's not stop here. What if I'll tell you that there is a constant time solution?

Yes! The inclusion-exclusion principle claims that if there are two finite sets $A,B$, the number of elements in their union can be expressed as $|A\cup B|=|A|+|B|-|A\cap B|$. This is a pretty popular combinatorics result. We can also extend this result and express a relation for the sum of their elements, namely

$\sum _{x\in A\cup B}x=\sum _{x\in A}x+\sum _{x\in B}x-\sum _{x\in A\cap B}x$

Implying this to our problem, have $A$ denote the multiples of 3 up to $n$ and $B$ the multiples of 5 up to $n$, the problem can be reduced to summing the multiples of 3, adding the sum of the multiples of 5, and subtracting the sum of the multiples of 15. For an arbitarily selected $k$, one can compute the multiples of $k$ up to $n$ via

$k+2k+3k+\ldots +\lfloor n/k\rfloor k=k(1+2+3+\ldots +\lfloor n/k\rfloor )=k{\frac {\lfloor n/k\rfloor (\lfloor n/k\rfloor +1)}{2}}$

Which makes the code more efficient. Now, in this case, the naïve solution can and does work, sure. This is not the point though! What it comes to show is that there are various solutions to any problem, and the naïve one will not work as you progress. Later problems will require you to come up with creative solutions, learn more math, optimize your code and follow the sites spirit.

See also

• List of computer science awards
• List of things named after Leonhard Euler

External links

• Official website
• Project Euler forum
• Project Euler Discord server
• Project Euler translations into several other languages
• Discussion about the Project Euler at YCombinator