 | |
Type of site | Problem Solving Website for Computational Mathematics |
|---|---|
| Created by | Colin Hughes |
| Website | projecteuler.net |
| Commercial | No |
| Registration | Free |
| Launched | 5 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
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
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.
- [math]\displaystyle{ \begin{align} \mathrm{sum}_{\text {3 or 5}}(n) & = \mathrm{sum}_3(n) + \mathrm{sum}_5(n) - \mathrm{sum}_{15}(n) \\[4pt] \mathrm{sum}_k(n) & = \sum_{i=1}^{\left \lfloor \frac{n-1}{k} \right \rfloor} ki \\[4pt] \sum_{i=1}^p ki & = \frac{kp(p+1)}{2} \end{align} }[/math]
Here, [math]\displaystyle{ \mathrm{sum}_k(n) }[/math] denotes the sum of multiples of [math]\displaystyle{ k }[/math] below [math]\displaystyle{ n }[/math]. In big O notation, the brute-force algorithm is [math]\displaystyle{ O\bigl(n\bigr) }[/math] and the efficient algorithm is [math]\displaystyle{ O\bigl(1\bigr) }[/math] (assuming constant time arithmetic operations).
See also
- List of computer science awards
- List of things named after Leonhard Euler
References
- ↑ Suri, Manil (12 October 2015). "The importance of recreational math". The New York Times. https://www.nytimes.com/2015/10/12/opinion/the-importance-of-recreational-math.html.
- ↑ Foote, Steven (2014). Learning to Program. Addison-Wesley learning series. Pearson Education. p. 249. ISBN 9780789753397. https://books.google.com/books?id=m4IhBQAAQBAJ&pg=PA249.
- ↑ James Somers (June 2011). "How I Failed, Failed, and Finally Succeeded at Learning How to Code - Technology". The Atlantic. https://www.theatlantic.com/technology/print/2011/06/how-i-failed-failed-and-finally-succeeded-at-learning-how-to-code/239855/. Retrieved 14 December 2013.
- ↑ "Project Euler (list of problems)". http://projecteuler.net/problems. Retrieved 14 March 2022.
- ↑ "News - Project Euler". https://projecteuler.net/news.
- ↑ 6.0 6.1 "Project Euler - About". http://projecteuler.net/about. Retrieved 4 April 2008.
- ↑ "Project Euler (Statistics)". https://projecteuler.net/statistics. Retrieved 27 April 2021.
- ↑ "Project Euler (News Archives)". https://projecteuler.net/news_archives. Retrieved 31 March 2015.
External links
- Links to Translation Projects into several other languages
 |  |