El Proyecto Euler (llamado así por Leonhard Euler ) es un sitio web dedicado a una serie de problemas computacionales destinados a ser resueltos con programas de computadora . [1] [2] El proyecto atrae a graduados y estudiantes interesados en matemáticas y programación informática . Desde su creación en 2001 por Colin Hughes, el Proyecto Euler ha ganado notoriedad y popularidad en todo el mundo. [3] Incluye 904 problemas al 25 de agosto de 2024, [4] con uno nuevo agregado aproximadamente cada semana. [5] Los problemas son de diferente dificultad, pero cada uno se puede resolver en menos de un minuto de tiempo de CPU utilizando un algoritmo eficiente en una computadora de potencia modesta. [6]
Se puede ver un foro específico para cada pregunta después de que el usuario haya respondido correctamente la pregunta dada. [6] Los problemas se pueden ordenar por ID, número resuelto y dificultad. Los participantes pueden seguir su progreso a través de niveles de logro basados en el número de problemas resueltos. Se alcanza un nuevo nivel por cada 25 problemas resueltos. Existen premios especiales para resolver combinaciones especiales de problemas. Por ejemplo, hay un premio por resolver cincuenta problemas con números primos. Existe un nivel especial "Eulerianos" para seguir el logro basado en los cincuenta solucionadores más rápidos de problemas recientes para que los miembros más nuevos puedan competir sin resolver problemas más antiguos. [7]
El primer problema del Proyecto Euler es Múltiplos de 3 y 5
Si enumeramos todos los números naturales menores de 10 que son múltiplos de 3 o 5, obtenemos 3, 5, 6 y 9. La suma de estos múltiplos es 23.
Encuentra la suma de todos los múltiplos de 3 o 5 menores que 1000.
Es un problema con una calificación del 5%, lo que indica que es uno de los más fáciles del sitio. El primer método que puede utilizar un principiante es un intento de fuerza bruta . Dado el límite superior de 1000 en este caso, es fácil lograr un intento de fuerza bruta en la mayoría de las computadoras domésticas actuales. A continuación se presenta un código Python que lo resuelve.
def resolver ( límite ): total = 0 para i en rango ( límite ): si i % 3 == 0 o i % 5 == 0 : total += yo devolver totalimprimir ( resolver ( 1000 ))Esta solución tiene una notación O grande de . Un usuario podría seguir perfeccionando su solución para cualquier problema dado. En este caso, existe una solución de tiempo constante para el problema.
El principio de inclusión-exclusión afirma que si hay dos conjuntos finitos , el número de elementos en su unión se puede expresar como . Este es un resultado combinatorio bastante popular. Se puede extender este resultado y expresar una relación para la suma de sus elementos, es decir
Aplicando esto al problema, denotamos los múltiplos de 3 hasta y los múltiplos de 5 hasta , el problema se puede reducir a sumar los múltiplos de 3, sumar la suma de los múltiplos de 5 y restar la suma de los múltiplos de 15. Para un seleccionado arbitrariamente , se pueden calcular los múltiplos de hasta mediante
Los problemas posteriores progresan (de forma no lineal) en dificultad, lo que requiere una metodología más creativa y una mayor comprensión de los principios matemáticos detrás de los problemas.
