Project Euler
Encyclopedia
Project Euler is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics
and computer programming
. , it includes 351 problems of varying difficulty, each solvable in less than a minute using an efficient algorithm on a modestly powered computer. A forum specific to each question may be viewed after the user has correctly answered the given question. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide and currently has more than 180 thousand users worldwide.
Participants can track their progress through thirteen achievement levels based on number of problems solved. A special Eulerians level exists to track achievement based on the fastest twenty solvers of recent problems so that newer members can compete without solving older problems.
A subset of the Project Euler problems was used in an APL programming contest held by Dyalog, an APL vendor.
Currently there are 50 sequences in the On-Line Encyclopedia of Integer Sequences(OEIS)
referencing Project Euler problems.
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
:
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
. , it includes 351 problems of varying difficulty, each solvable in less than a minute using an efficient algorithm on a modestly powered computer. A forum specific to each question may be viewed after the user has correctly answered the given question. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide and currently has more than 180 thousand users worldwide.
Participants can track their progress through thirteen achievement levels based on number of problems solved. A special Eulerians level exists to track achievement based on the fastest twenty solvers of recent problems so that newer members can compete without solving older problems.
A subset of the Project Euler problems was used in an APL programming contest held by Dyalog, an APL vendor.
Currently there are 50 sequences in the On-Line Encyclopedia of Integer Sequences(OEIS)
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
referencing Project Euler problems.
Example problem and solutions
The first Project Euler problem isIf 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
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
:
Set TOTAL to 0;
for every number NUM from 1 to 999 do
if NUM mod 3 = 0 or if NUM mod 5 = 0 then
add NUM to TOTAL;
output TOTAL
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
Inclusion-exclusion principle
In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...
and a closed form
Closed-form expression
In mathematics, an expression is said to be a closed-form expression if it can be expressed analytically in terms of a bounded number of certain "well-known" functions...
summation
Summation
Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed may be integers, rational numbers,...
formula.
-
Here,
denotes the sum of multiples of 
below 
.
In Big O notationBig O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
, the brute-force algorithm is O(n) and the efficient algorithm is O(1) (assuming constant time arithmetic operations).
External links
- Home page
- "How I Failed, Failed, and Finally Succeeded at Learning How to Code: The programming website Project Euler provides a plan for how to learn anything in fun, discrete steps" -(James Somer, The Atlantic)
- Jakumo : Project Euler In Russian
- EulerES : Project Euler In Spanish
- EulerDZ : Project Euler In French