Project Euler
   HOME

TheInfoList



OR:

Project Euler (named after
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
) is a
website A website (also written as a web site) is a collection of web pages and related content that is identified by a common domain name and published on at least one web server. Examples of notable websites are Google, Facebook, Amazon, and Wi ...
dedicated to a series of
computational problem In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational probl ...
s intended to be solved with
computer program A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...
s. The project attracts graduates and students interested in mathematics and
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide. It includes over 830 problems as of 23 March 2023, 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 CPU time (or process time) is the amount of time for which a central processing unit (CPU) was used for processing instructions of a computer program or operating system, as opposed to elapsed time, which includes for example, waiting for inpu ...
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.
Although 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: ''total'' := 0 for ''NUM'' from 1 through 999 do if ''NUM'' mod 3 = 0 or ''NUM'' mod 5 = 0 then ''total'' := ''total'' + ''NUM'' return ''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 In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as : , A \cu ...
and a closed-form summation formula. : \begin \mathrm_(n) & = \mathrm_3(n) + \mathrm_5(n) - \mathrm_(n) \\ pt \mathrm_k(n) & = \sum_^ ki \\ pt \sum_^p ki & = \frac \end Here, \mathrm_k(n) denotes the sum of multiples of k below n. In big O notation, the brute-force algorithm is O\bigl(n\bigr) and the efficient algorithm is O\bigl(1\bigr) (assuming constant time arithmetic operations).


See also

* List of computer science awards *
List of things named after Leonhard Euler 200px, Leonhard Euler (1707–1783) In mathematics and physics, many topics are named in honor of Swiss mathematician Leonhard Euler (1707–1783), who made many important discoveries and innovations. Many of these items named after Euler inclu ...


References


External links

* {{Official website
Project Euler forum
* Links t
Translation Projects
into several other languages Mathematics websites Programming contests Problem solving Puzzles British educational websites Mathematics education in the United Kingdom