Project Euler

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Logo de Project Euler
Project Euler

URL projecteuler.net
Commercial non
Type de site résolution de problèmes
Langue(s) anglais[Note 1]
Inscription gratuite
Créé par Colin Hughes, alias euler
Lancement 5 octobre 2001
État actuel suspendu (uniquement la consultation des problèmes est possible)

Project Euler est un site web proposant une série de problèmes mathématiques conçus pour être résolus à l'aide de programmes informatiques. Le but du projet est d'attirer des adultes et des élèves intéressés par les mathématiques et l’informatique. Il comprend actuellement près de 480 problèmes[Note 2],[1] de difficulté variable, chacun pouvant être résolu en principe en moins d'une minute par un algorithme efficace sur un ordinateur de puissance modeste. De nouveaux problèmes sont progressivement ajoutés, actuellement au rythme d'un par semaine, depuis la création du site en 2001. Un forum spécifique à chaque problème est accessible aux utilisateurs qui l'ont résolu. Une section Scores classe également les membres selon le nombre de problèmes résolus. Il existe quatorze niveaux de classement selon le nombre de problèmes résolus, ainsi qu'un classement spécial basé sur la vitesse de résolution des derniers problèmes parus.

Depuis la création du site en 2001, plus de 200 000 utilisateurs se sont enregistrés sur le site[2].

Exemple de problème et solutions[modifier | modifier le code]

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

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 à 1000[Note 4].

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 5] par rapport à un algorithme naïf. L'algorithme brute-force examine chaque entier naturel inférieur à 1000 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 1000 opérations à quelques-unes en utilisant le principe d'inclusion-exclusion et une formule de sommation :

\mathrm{sum}_{\text{3 ou 5}}(n+1) = \mathrm{sum}_3(n+1)+\mathrm{sum}_5(n+1)-\mathrm{sum}_{15}(n+1)= \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 = \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)

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

Implémentation en Python :

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

Grâce à cet algorithme, la solution pour une borne supérieure à 10 000 000 peut être obtenue presque aussi rapidement que pour 1000. 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).

Suspension[modifier | modifier le code]

Depuis le dimanche 15 Juin 2014, le site est en suspension totale. En effet, en consultant le site, le message suivant s'affiche :

"Due to the discovery of a serious security issue a decision was made on Sunday 15 June 2014 to take down the website. The full extent of the issue is still being investigated but in an attempt to be as honest as possible to our members we must make you aware that we have reason to suspect that all or parts of the database may have compromised. Passwords at Project Euler are strongly encrypted using a one-way hash, but if you use the same password at other websites then it is strongly advised that you change it. We are extremely sorry for this inconvenience. At this time we can provide no more information and there is no indication when Project Euler will return."

Ce qui veut dire que la base de donnée du projet a été attaquée, et une décision de le rendre hors ligne a été prise. Aucune indication n'a été fournie quant à la date de retour du projet[3].

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Depuis 2010, Project Euler existe aussi en français et en russe.
  2. 476 problèmes au 1er Juillet 2014
  3. L'énoncé original est « 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. »
  4. C'est le OU inclusif qui est utilisé ici.
  5. En informatique, quand un algorithme répond correctement au problème posé, on cherche souvent à l'optimiser. On veut que l'algorithme utilise le moins de temps et de mémoire possible. Voir ici pour plus de précisions.

Références[modifier | modifier le code]

  1. (en) « Project Euler - Problems », sur projecteuler.net (consulté le 01 Juillet 2014)
  2. (en) « Project Euler - Statistics », sur projecteuler.net (consulté le 19 septembre 2012)
  3. « Project Euler »