Project Euler

Une traduction du premier problème est[Note 2] :

« Si on liste tous les entiers naturels inférieurs à 10 qui sont multiples de 3 ou de 5, on obtient 3, 5, 6 et 9. La somme de ces nombres est 23. Trouvez la somme de tous les multiples de 3 ou de 5 inférieurs à 1 000[Note 3]. »

Bien que ce problème soit l'un des plus simples du site, il permet d'illustrer le gain de temps potentiel d'un algorithme efficace[Note 4] par rapport à un algorithme naïf. L'algorithme brute-force examine chaque entier naturel inférieur à 1 000 et actualise la somme de ceux qui remplissent les critères. Cette méthode est facile à implémenter ; en pseudo-code, cela peut s'écrire :

initialiser SOMME à 0;
  pour n variant de 1 à 999 faire
    si n est un multiple de 3 ou de 5 alors // Autrement dit si n est divisible par 3 ou par 5
      ajouter n à SOMME;
  fait;
renvoyer SOMME

Cependant, pour les problèmes plus complexes, trouver un algorithme efficace devient indispensable. Pour cet exemple, nous pouvons réduire 1 000 opérations à quelques-unes en utilisant le principe d'inclusion-exclusion et une formule de sommation :

${\textstyle \mathrm {sum} _{\text{3 ou 5}}(n+1)=\mathrm {sum} _{3}(n+1)+\mathrm {sum} _{5}(n+1)-\mathrm {sum} _{15}(n+1)}$

${\displaystyle ={\frac {3}{2}}\left(\left\lfloor {\frac {n}{3}}\right\rfloor \left(\left\lfloor {\frac {n}{3}}\right\rfloor +1\right)\right)+{\frac {5}{2}}\left(\left\lfloor {\frac {n}{5}}\right\rfloor \left(\left\lfloor {\frac {n}{5}}\right\rfloor +1\right)\right)-{\frac {15}{2}}\left(\left\lfloor {\frac {n}{15}}\right\rfloor \left(\left\lfloor {\frac {n}{15}}\right\rfloor +1\right)\right)}$

${\displaystyle =\sum _{i=1}^{\lfloor {\frac {n}{3}}\rfloor }3i+\sum _{i=1}^{\lfloor {\frac {n}{5}}\rfloor }5i-\sum _{i=1}^{\lfloor {\frac {n}{15}}\rfloor }15i}$

Où ${\displaystyle \mathrm {sum} _{k}(n+1)}$ désigne la somme des multiples de ${\displaystyle k}$ inférieurs à ${\displaystyle n+1}$ et ${\displaystyle \lfloor .\rfloor }$ désigne l'arrondi à l'entier inférieur.

Implémentation en Python :

def sum_1_to_n(n):
   return n * (n + 1) / 2
def sum_multiples(limit, a):
   return sum_1_to_n((limit - 1) // a) * a
sum_multiples(1000, 3) + sum_multiples(1000, 5) - sum_multiples(1000, 15)

Grâce à cet algorithme, la solution pour une borne supérieure à 10 000 000 peut être obtenue presque aussi rapidement que pour 1 000. En notation de Landau, l'algorithme brute-force est en O(n) tandis que l'algorithme efficace est en O(1) (si on considère que le coût des opérations arithmétiques est constant).

À ce jour, il existe différentes traductions du Projet Euler (classées par ordre alphabétique) :

• (en) Site officiel du Projet Euler