Project Euler
Type of site | Series of computational mathematics problems |
|---|---|
| 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 over 850 problems as of 12 August 2023,[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]
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 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, as follows. Let [math]\displaystyle{ \mathrm{sum}_k(n) }[/math] denote the sum of multiples of [math]\displaystyle{ k }[/math] below [math]\displaystyle{ n }[/math]. Then we have:
- [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]
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.
- ↑ "Recent Problems - Project Euler". https://projecteuler.net/recent.
- ↑ "News - Project Euler". https://projecteuler.net/news.
- ↑ 6.0 6.1 "About - Project Euler". https://projecteuler.net/about.
- ↑ "Project Euler (News Archives)". https://projecteuler.net/news_archives. Retrieved 31 March 2015.
External links
- Project Euler forum
- Project Euler translations into several other languages
- Discussion about the Project Euler at YCombinator
 |  |
