Project Euler

Project Euler

Type of site	Problem Solving Website
Created by	Colin Hughes (aka Euler)
URL	projecteuler.net
Commercial	No
Registration	Free

Project Euler is a website dedicated to a series of math problems intended to be solved with computer programs. The project is aimed at attracting adults and students interested in mathematics and computer programming. It currently consists of more than 200 problems of varying difficulty, and each problem is designed to execute in under a minute using an efficient algorithm on a modestly powered computer. New questions have been periodically added since the project's creation in 2001. The site features forums specific to each question, accessible after the user has correctly answered the given question. There is also a high scorers section, accessible to logged-in users, which ranks users by the number of problems solved. There are 5 different scoring levels (denoted by platonic solids), plus a special Eulerians level that contains the members who have solved at least half of the most recent 25 problems.

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 examples in different programming languages:

Python:

print sum(x for x in xrange(1, 1000) if x%3==0 or x%5 == 0)

C++:

#include <iostream>
using namespace std;
int main( ) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if ( i % 3 == 0 || i % 5 == 0 )
      sum += i;
  cout << sum << endl;
  return 0;
}

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

$sum(n)=\sum _{i=1}^{\lfloor {\frac {n}{3}}\rfloor }3i+\sum _{i=1}^{\lfloor {\frac {n}{5}}\rfloor }5i-\sum _{i=1}^{\lfloor {\frac {n}{15}}\rfloor }15i$

$\sum _{i=1}^{n}ki=k{\frac {(n)(n+1)}{2}}$

Python implementation:

def sum1toN(n):
   return n * (n + 1) / 2

def sumMultiples(limit, a):
   return sum1toN((limit - 1) / a) * a

sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)

With this algorithm, the solution for 10,000,000 can be computed just as quickly as for 1000. In Big O notation, the brute-force algorithm is O(n) and the efficient algorithm is O(log n).

See Also

List of topics named after Leonhard Euler

External links

• Home page