Misplaced Pages

Project Euler

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Website and series of mathematical challenges
Project Euler
Type of siteSeries of computational mathematics problems
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. 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. It includes 923 problems as of December 22 2024, 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 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.

It is a 5% rated problem, indicating it is one of the easiest on the site. The initial approach a beginner can come up with is a bruteforce attempt. Given the upper bound of 1000 in this case, a bruteforce is easily achievable for most current home computers. A Python code that solves it is presented below. 

def solve(limit):
    total = 0
    for i in range(limit):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total
print(solve(1000))

This solution has a Big O Notation of O ( n ) {\displaystyle O(n)} . A user could keep refining their solution for any given problem further. In this case, there exists a constant time solution for the problem.

The inclusion-exclusion principle claims that if there are two finite sets A , B {\displaystyle A,B} , the number of elements in their union can be expressed as | A ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|} . This is a pretty popular combinatorics result. One can extend this result and express a relation for the sum of their elements, namely

∑ x ∈ A ∪ B x = ∑ x ∈ A x + ∑ x ∈ B x − ∑ x ∈ A ∩ B x {\displaystyle \sum _{x\in A\cup B}x=\sum _{x\in A}x+\sum _{x\in B}x-\sum _{x\in A\cap B}x}

Applying this to the problem, have A {\displaystyle A} denote the multiples of 3 up to n {\displaystyle n} and B {\displaystyle B} the multiples of 5 up to n {\displaystyle n} , the problem can be reduced to summing the multiples of 3, adding the sum of the multiples of 5, and subtracting the sum of the multiples of 15. For an arbitrarily selected k {\displaystyle k} , one can compute the multiples of k {\displaystyle k} up to n {\displaystyle n} via

k + 2 k + 3 k + … + ⌊ n / k ⌋ k = k ( 1 + 2 + 3 + … + ⌊ n / k ⌋ ) = k ⌊ n / k ⌋ ( ⌊ n / k ⌋ + 1 ) 2 {\displaystyle k+2k+3k+\ldots +\lfloor n/k\rfloor k=k(1+2+3+\ldots +\lfloor n/k\rfloor )=k{\frac {\lfloor n/k\rfloor (\lfloor n/k\rfloor +1)}{2}}}

Later problems progress (non-linearly) in difficulty, requiring more creative methodology and higher understanding of the mathematical principles behind the problems.

See also

References

  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. "Recent Problems - Project Euler". Retrieved 23 March 2023.
  5. "News - Project Euler". projecteuler.net. Retrieved 27 April 2021.
  6. ^ "About - Project Euler". Retrieved 23 March 2023.
  7. "Project Euler (News Archives)". Retrieved 31 March 2015.

External links

Categories: