Project Euler

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Project Euler
Euler
Type of site
Problem Solving Website for Computational Mathematics
Created byColin Hughes
URLprojecteuler.net
CommercialNo
RegistrationFree
Launched5 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.[1][2] 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.[3] It includes 800 problems as of 30 May 2022,[4] with a new one added approximately every week.[5] 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.[6] As of 27 April 2021, Project Euler has more than 1,000,000 users who have solved at least one problem, in over 100 different programming languages.[7]

Features of the site[edit]

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

Example problem and solutions[edit]

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 and a closed-form summation formula.

Here, denotes the sum of multiples of below . In big O notation, the brute-force algorithm is and the efficient algorithm is (assuming constant time arithmetic operations).

See also[edit]

References[edit]

  1. ^ Suri, Manil (12 October 2015). "The importance of recreational math". The New York Times. Retrieved 5 June 2018.
  2. ^ Foote, Steven (2014). Learning to Program. Addison-Wesley learning series. Pearson Education. p. 249. ISBN 9780789753397.
  3. ^ James Somers (June 2011). "How I Failed, Failed, and Finally Succeeded at Learning How to Code - Technology". The Atlantic. Retrieved 14 December 2013.
  4. ^ "Project Euler (list of problems)". Retrieved 14 March 2022.{{cite web}}: CS1 maint: url-status (link)
  5. ^ "News - Project Euler". projecteuler.net. Retrieved 27 April 2021.
  6. ^ a b "Project Euler - About". Retrieved 4 April 2008.
  7. ^ "Project Euler (Statistics)". Retrieved 27 April 2021.{{cite web}}: CS1 maint: url-status (link)
  8. ^ "Project Euler (News Archives)". Retrieved 31 March 2015.

External links[edit]