Project Euler

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 adults 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 over 700 problems,[4] with a new one added once every one or two weeks. 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. As of 5 April 2020, Project Euler has more than 1,000,000 users, from all over the world, who have solved at least one problem.[5]

Project Euler
Type of site
Problem Solving Website
Created byColin Hughes
URLprojecteuler.net
CommercialNo
RegistrationFree
LaunchedOctober 5, 2001

Features of the site

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.[7]

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 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 O(n) and the efficient algorithm is O(1) (assuming constant time arithmetic operations).

See also

References
  1. Suri, Manil (2015-10-12). "The importance of recreational math". The New York Times. Retrieved 2018-06-05.
  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 2013-12-14.
  4. "Project Euler (list of problems)". Retrieved 2020-05-05.
  5. "Project Euler (Statistics) - login required". Retrieved 2019-06-10.
  6. "Project Euler - About". Retrieved 2008-04-04.
  7. "Project Euler (News Archives)". Retrieved 2015-03-31.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.