Project Euler

Project Euler
Type of site	Series of computational mathematics problems
Created by	Colin Hughes
URL	projecteuler.net
Commercial	No
Registration	Free
Launched	5 October 2001

Last updated October 10, 2024

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 911 problems as of October 9 2024,^[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.

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.

defsolve(limit):total=0foriinrange(limit):ifi%3==0ori%5==0:total+=ireturntotalprint(solve(1000))

This solution has a Big O Notation of $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$ , the number of elements in their union can be expressed as $|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

$\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$ denote the multiples of 3 up to $n$ and $B$ the multiples of 5 up to $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$ , one can compute the multiples of $k$ up to $n$ via

$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.

Related Research Articles

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

The number $e$ is a mathematical constant approximately equal to 2.71828 that is the base of the natural logarithm and exponential function. It is sometimes called Euler's number, after the Swiss mathematician Leonhard Euler, though this can invite confusion with Euler numbers, or with Euler's constant, a different constant typically denoted $. Alternatively, e can be called Napier's constant after John Napier. The Swiss mathematician Jacob Bernoulli discovered the constant while studying compound interest.$

The knapsack problem is the following problem in combinatorial optimization:

Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form $where n is a given positive nonsquare integer, and integer solutions are sought for x and y . In Cartesian coordinates, the equation is represented by a hyperbola; solutions occur wherever the curve passes through a point whose x and y coordinates are both integers, such as the trivial solution with x = 1 and y = 0. Joseph Louis Lagrange proved that, as long as n is not a perfect square, Pell's equation has infinitely many distinct integer solutions. These solutions may be used to accurately approximate the square root of n by rational numbers of the form x / y .$

In number theory, Waring's problem asks whether each natural number k has an associated positive integer s such that every natural number is the sum of at most s natural numbers raised to the power k. For example, every natural number is the sum of at most 4 squares, 9 cubes, or 19 fourth powers. Waring's problem was proposed in 1770 by Edward Waring, after whom it is named. Its affirmative answer, known as the Hilbert–Waring theorem, was provided by Hilbert in 1909. Waring's problem has its own Mathematics Subject Classification, 11P05, "Waring's problem and variants".

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In mathematics, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the smallest integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. Formulas for calculating primes do exist; however, they are computationally very slow. A number of constraints are known, showing what such a "formula" can and cannot be.

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

In mathematics, Farkas' lemma is a solvability theorem for a finite system of linear inequalities. It was originally proven by the Hungarian mathematician Gyula Farkas. Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization. It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming. Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements.

The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers $such that$

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proven by Euclid in his work Elements. There are several proofs of the theorem.

A decimal representation of a non-negative real number $r$ is its expression as a sequence of symbols consisting of decimal digits traditionally written with a single separator: $Here . is the decimal separator, k is a nonnegative integer, and are digits, which are symbols representing integers in the range 0, ..., 9.$

In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete bipartite subgraphs), needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).

In stochastic analysis, a rough path is a generalization of the notion of smooth path allowing to construct a robust solution theory for controlled differential equations driven by classically irregular signals, for example a Wiener process. The theory was developed in the 1990s by Terry Lyons. Several accounts of the theory are available.

In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.

In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem.

References

↑ Suri, Manil (12 October 2015). "The importance of recreational math". The New York Times . Retrieved 5 June 2018.
↑ Foote, Steven (2014). Learning to Program. Addison-Wesley learning series. Pearson Education. p. 249. ISBN 9780789753397.
↑ James Somers (June 2011). "How I Failed, Failed, and Finally Succeeded at Learning How to Code - Technology". The Atlantic. Retrieved 14 December 2013.
↑ "Recent Problems - Project Euler" . Retrieved 23 March 2023.
↑ "News - Project Euler". projecteuler.net. Retrieved 27 April 2021.
1 2 "About - Project Euler" . Retrieved 23 March 2023.
↑ "Project Euler (News Archives)" . Retrieved 31 March 2015.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[about-6] 1 2 "About - Project Euler" . Retrieved 23 March 2023.

[7] "Project Euler (News Archives)" . Retrieved 31 March 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]