robot de la enciclopedia para niños

Project Euler para niños

Enciclopedia para niños
Datos para niños
Project Euler
Leonhard Euler.jpg
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
Ranking Alexa 41,408 (mayo de 2016)

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. Incluye más de 700 problemas, 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. 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.

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.

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

Problemas y soluciones de ejemplo

El primer problema de Project Euler es:

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.

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:

\begin{align}
\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{align}

Aquí, \mathrm{sum}_k(n) denota una suma de varias k menores de 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).

Véase también

Kids robot.svg En inglés: Project Euler Facts for Kids

kids search engine
Project Euler para Niños. Enciclopedia Kiddle.