Project Euler

Project Euler
Información general
Dominio	projecteuler.net
Tipo	Sitio web de resolución de problemas
Comercial	No
Idiomas disponibles	Inglés
En español	No
Estado actual	Activo
Gestión
Desarrollador	Colin Hughes
Lanzamiento	5 de octubre de 2001
Estadísticas
Usuarios registrados	> 650 000

Project Euler (Proyecto Euler, llamado así por el matemático Leonhard Euler) es un sitio web dedicado a una serie de problemas matemáticos diseñados para ser resueltos por programas computacionales. El proyecto atrae a adultos y a estudiantes interesados en matemáticas y programación informática. Desde su creación en 2001 por Colin Hughes, Project Euler ha ganado notabilidad y popularidad internacional.[2]​ Incluye más de 700 problemas,[3]​ con uno nuevo siendo agregado cada fin de semana, excepto durante el verano. Los problemas varían de dificultad, pero todos son resolubles en menos de un minuto usando un algoritmo eficiente.[4]​ Un fórum específico para cada pregunta puede ser visitado después de que el usuario haya respondido correctamente a una pregunta dada. Para noviembre de 2016, Project Euler alcanzó a 650 000 usuarios alrededor del mundo que han resuelto al menos un problema.[5]​

Los participantes pueden consultar su progreso mediante logros basados en el número de problemas resueltos. Un nuevo logro es alcanzado por cada 25 problemas resueltos. Existen premios especiales por resolver combinaciones de problemas especiales; por ejemplo, hay un logro ofrecido por resolver cincuenta problemas numerados como primos. También existe un nivel especial para registrar logros basados en los cincuenta primeros usuarios que resuelven problemas nuevos.[6]​

Un subset de problemas de Project Euler fue usado en un concurso de programación de APL.[7]​ Hay 97 secuencias en la Enciclopedia Electrónica de Secuencias de Enteros (OEIS) referenciadas en problemas de Project Euler.[8]​

Problemas y soluciones de ejemplo

El primer problema de Project Euler es:[9]​

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.

Si listamos todos los números naturales menores de 10 que son múltiplos de 3 o 5, conseguimos 3, 5, 6 y 9. La suma de estos múltiplos de 23. Encuentra la suma de todos los múltiplos de 3 o 5 menores de 1000.[note 1]​

Aunque este problema es mucho más simple que los tradicionales, sirve para ilustrar la gran diferencia que un algoritmo eficiente hace. El algoritmo de fuerza bruta examina cada número natural menor a 1000 y realiza una suma de aquellos que cumplen estos requisitos. Este método es sencillo de implementar, como se indica en el siguiente pseudocódigo:

Set TOTAL to 0;
for NUM from 1 through 999 do
  if NUM mod 3 = 0 or if NUM mod 5 = 0 then
    add NUM to TOTAL;
output TOTAL

Para problemas más difíciles, se vuelve más importante encontrar un algoritmo eficiente. Para este problema, podemos reducir 1000 operaciones a unas pocas usando el principio de inclusión-exclusión y usando una sumatoria de forma cerrada:

${\displaystyle {\begin{aligned}\mathrm {sum} _{\text{3 o 5}}(n)&=\mathrm {sum} _{3}(n)+\mathrm {sum} _{5}(n)-\mathrm {sum} _{15}(n)\\\mathrm {sum} _{k}(n)&=\sum _{i=1}^{\left\lfloor {\frac {n-1}{k}}\right\rfloor }ki\\\sum _{i=1}^{p}ki&=k{\frac {(p+1)p}{2}}\end{aligned}}}$

Aquí, ${\displaystyle \mathrm {sum} _{k}(n)}$ denota una suma de varias ${\displaystyle k}$ menores de ${\displaystyle n}$.

En una cota superior asintótica, el algoritmo de fuerza bruta es O(n) y el algoritmo eficiente es O(1) (asumiendo tiempo constante de operaciones aritméticas).

Notas

1. Este es el O inclusivo, no el O exclusivo

Referencias

1. «Projecteuler.net Site Overview». Alexa Internet. Archivado desde el original el 21 de julio de 2016. Consultado el 30 de mayo de 2016. 
2. James Somers (Junio de 2011). «How I Failed, Failed, and Finally Succeeded at Learning How to Code - Technology». The Atlantic. Consultado el 14 de diciembre de 2013. 
3. «Project Euler (lista de problemas)». Consultado el 8 de abril de 2022. 
4. «Project Euler - About». Consultado el 4 de abril de 2008. 
5. Hughes, Colin. «About - Project Euler». projecteuler.net. Consultado el 6 de julio de 2016. 
6. «Project Euler (Noticias)». Consultado el 31 de marzo de 2015. 
7. «APL programming contest problem list». Consultado el 17 de agosto de 2014. 
8. «OEIS sequences referencing Project Euler problems». Consultado el 30 de mayo de 2016. 
9. «Project Euler Problem 1». Project Euler. Consultado el 1 de marzo de 2017. 

Enlaces externos

• Página principal
• Jakumo: Project Euler en ruso
• Project Euler en rumano(caché)
• Problemas de Project Euler en ruso
• Problemas de Project Euler usando programación (los usuarios deben subir código para resolver el problema en vez de la respuesta)

• Datos: Q168430