Project Euler

Archiu:Leonhard Euler.jpg

Project Euler

Project Euler (Proyecte Euler, cridat aixina pel matemàtic Leonhard Euler) és un lloc web dedicat a una série de problemes matemàtics dissenyats per a ser resolts per programes computacionals. El proyecte atrau a adults i a estudiants interessats en matemàtiques i programació informàtica. Des de la seua creació en 2001 per Colin Hughes, Project Euler ha guanyat notabilidad i popularitat internacional. Inclou més de 700 problemes, en un nou sent agregat cada fi de semana, llevat durant l'estiu. Els problemes varien de dificultat, pero tots són resolubles en menys d'un minut usant un algoritme eficient. Un fórum específic per a cada pregunta pot ser visitat en acabant de que l'usuari haja respost correctament a una pregunta donada. Per a novembre de 2016, Project Euler va alcançar a 650 000 usuaris al voltant del món que han resolt a lo manco un problema.

Els participants poden consultar el seu progrés per mig de guanys basats en el número de problemes resolts. Un nou guany és alcançat per cada 25 problemes resolts. Existixen premis especials per resoldre combinacions de problemes especials; per eixemple, hi ha un guany oferit per resoldre cinquanta problemes numerats com primers. També existix un nivell especial per a registrar guanys basats en els cinquanta primers usuaris que resolen problemes nous.

Un subset de problemes de Project Euler va ser usat en un concurs de programació d'APL. Hi ha 97 seqüències en l'Enciclopèdia Electrònica de Seqüències de Sancers (OEIS) referenciadas en problemes de Project Euler.

Problemes i solucions d'eixemple

El primer problema de Project Euler és:

Encara que este problema és molt més simple que els tradicionals, servix per a ilustrar la gran diferència que un algoritme eficient fa. L'algoritme de força bruta examina cada número natural menor a 1000 i realisa una suma d'aquells que complixen estos requisits. Este método és senzill d'implementar, com s'indica en el següent 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

Per a problemes més difícils, es torna més important trobar un algoritme eficient. Per a este problema, podem reduir 1000 operacions a unes poques usant el principi d'inclusió-exclusió i usant una sumatoria de forma tancada:

$\begin{array}{cc}{\mathrm{s}\mathrm{u}\mathrm{m}}_{\text{3 o 5}}(n)& ={\mathrm{s}\mathrm{u}\mathrm{m}}_3(n)+{\mathrm{s}\mathrm{u}\mathrm{m}}_5(n)-{\mathrm{s}\mathrm{u}\mathrm{m}}_{15}(n)\\ {\mathrm{s}\mathrm{u}\mathrm{m}}_k(n)& =\sum _{i=1}^{\lfloor \frac{n-1}{k}\rfloor }ki\\ \sum _{i=1}^{p}ki& =k\frac{(p+1)p}{2}\end{array}$

Ací, ${\mathrm{s}\mathrm{u}\mathrm{m}}_k(n)$ denota una suma de vàries $k$ menors de $n$.

En una cota superior asintòtica, l'algoritme de força bruta és O(n) i l'algoritme eficient és O(1) (assumint temps constant d'operacions aritmètiques).