Programmer pour le fun 11


Amis des casse-tête mathématiques ardus et de la programmation d’algorithmes optimisés, bonjour!

Je viens de découvrir Project Euler.net, et j’ai honte de ne pas l’avoir trouvé avant. Ce site propose 233 problèmes (et environ un de plus chaque semaine environ) pouvant parfois être résolus avec un papier et un crayon propulsé par un cerveau en ébullition, mais pour la plupart requièrent  quelques lignes de code bien pensées et un stupide esclave électronique pour les exécuter.

Une fois inscrit sur le site, vous pouvez soumettre vos solutions aux problèmes dans l’ordre qui vous plait et chaque bonne réponse vous apporte instantanément:

  • la possibilité d’accéder à un forum où les solutions sont comparées et discutées. C’est en général là qu’on commence à avoir mal au front, quand on découvre des algorithmes 1000x plus rapides que ceux qu’on s’est escrimé à mettre au point, ou pire, la petite formule qui tue…
  • un bon point. Après 25 bonnes réponses vous entrez dans le tableau des scores et pouvez espérer rejoindre un jour la vingtaine de mutants qui ont résolu tous les problèmes jusqu’ici.

Il faut dire que les premiers problèmes sont relativement simples, par exemple les 17 que j’ai déjà résolus sont :

  • additionner tous les entiers intérieurs à 1000 qui sont multiples de 3 ou 5
  • trouver la somme de tous les nombres pairs de la suite de Fibonacci inférieurs à 4’000’000
  • trouver le plus grand facteur premier de 600’851’475’143
  • trouver le plus grand palindrome formé par le produit de 2 nombres de 3 chiffres
  • quel est le plus petit nombre divisible par tous les entiers de 1 à 20 ? (facile. celui là je l’ai fait à la main)
  • quelle est la différence entre le carré de la somme des 100 premiers entiers et la somme du carré de ces même nombres ?
  • trouver le 10001ème nombre premier
  • trouver le plus grand produit de 5 chiffres consécutifs dans un nombre à 1000 chiffres
  • trouver le seul triplet pythagoricien dont la somme a+b+c=1000
  • calculer la somme des nombres premiers inférieurs à 2’000’000
  • quel est le premier nombre triangulaire ayant plus de 500 diviseurs ?
  • quels sont les 10 premiers chiffres de la somme de 100 nombre de 50 chiffres donnés?
  • trouver le nombre inférieur à 1’000’000 générant la plus longue suite de Syracuse
  • en partant d’un coin d’une grille de 20×20, combien y’a-t-il de chemins au coin opposé ? (j’ai déjà vu ça quelque part…)
  • quelle est la somme des chiffres de  21000?
  • quel est le premier terme supérieur à 101000 de la suite de Fibonacci ? (et si je vous disais qu’on peut le trouver sans calculer les termes précédents ?)
  • trouver la somme des chiffres de 100! (factorielle…)

Certains de ces problèmes exigent de pouvoir manipuler de grands nombres, ce qui est une force du langage Python, que j’aime de plus en plus. On peut par exemple obtenir la somme des chiffres de la factorielle de 100 en une seule ligne* combinant la programmation fonctionnelle et la fonction reduce (un des piliers de la puissance de Google):

reduce(lambda x, y: x + y, [int(i) for i in str(reduce(lambda x, y: x * y, range(1, 100)))])

Bon, jusqu’ici j’ai fait le facile : même avec une approche un peu brutale, on s’en sort. Mais rapidement la complexité fait son apparition au carré : au niveau mathématique et au niveau algorithmique, condamnant le programmeur peu subtil à patienter des minutes, des heures ou des siècles devant un sablier virtuel …

Je vois encore quelques problèmes liés à des sujets déjà abordés sur Dr.Goulu comme:

Il y a encore environ entre 20 et 50 problèmes que j’espère pouvoir résoudre à raison d’un  par soirée.

Après, ce sera l’enfer mais j’espère vous y retrouver, ami lecteur … (insérer un rire sardonique ici)

Note* dans le forum on découvre une solution en 13 caractères seulement, en APL évidemment: +/ ». »0″:!100x

  • http://mathblogger.free.fr Bruno K.

    Le handicapé de l’anglais que je suis te remercie pour les traductions. Je vais pouvoir me plonger dans ces problèmes de façon plus sereine.

  • http://eric.cabrol.free.fr/dotclear/ Eric C.

    Un peu dans le même genre, quoique avec un vernis commercial puisqu’il faut disposer de Matlab, le « programming contest » : http://www.mathworks.com/contest/overview.html

  • http://ouvertures.info kalvin

    J’admire mais je n’ose même pas m’inscrire ….

  • http://anceps.canalblog.com Anceps

    Si parfois le crayon suffit, il est en tout cas indispensable pour bon nombre de problèmes qui ne sont pas résolubles en les programmant directement.

    J’y épuise régulièrement ma réserve de papier brouillon et autres enveloppes gardées pour l’occasion (sans parler du temps, évidemment) :
    http://anceps.canalblog.com/archives/2006/02/14/1369625.html

  • http://goulu.net Dr. Goulu

    Enfin : 25 problèmes résolus, j’entre dans le classement.
    Mais je ne suis pas sur de continuer à ce rythme …

  • http://drgoulu.com Dr. Goulu

    50 problèmes résolus (en trichant à peine…). Les suivants sont TRES difficiles…

  • http://lastrophoto.fr Guib.

    Yes Merci pour le lien, très intéressant ces problèmes de math/algo, Je me suis inscrit hier soir et j’en suis à 5 problèmes résolus en programmant en Python….

  • Pingback: Combien de nombres palindromes > N ? « Dr. Goulu()

  • http://www.scalpa.info pascal

    Une petite quête sur google à la recherche d’une « soluce excel » pour ce problème sûrement basique, mais insurmontable pour le « nul en maths » que j’ai toujours été m’a amené sur votre blog où j’espère que ma question trouvera un écho :
    Je suis instit, et je travaille (j’essaie…) sur les multiples de 2, 3, 5, 9, 10. J’aurai aimé élaborer une feuille sous excel qui me permettrait de proposer(une fois imprimée) des exos à mes élèves:

    Des nombres judicieusement(cad répondant à une ou des contrainte(s) liée(s) à leur divisibilité) et aléatoirement tirés seraient inscrits dans la première colonne du tableau et les enfants n’auraient plus qu’à mettre une croix dans la ou les colonnes qui vérifieraient la divisibilité….
    Oulà mon explication me paraît bien obscure!
    ex.
    ____|2|3|5|9|10|
    356 |x|o|o|o|o |
    540 |x|3|o|x|o |

    etc.
    La difficulté que je ne sais pas surmonter : comment être sûr que le nombre tiré aléatoirement (356, 540, …) ne soit multiple que des contraintes données? Alea.entre.bornes n’est pas suffisant.

    merci de votre aide
    pascale

    • http://drgoulu.com Dr. Goulu

      Que voilà un joli problème. Après un peu de réflexion, je le prendrais à l’envers, en partant du « corrigé ».

      Dans votre tableau Excel, commencez par mettre des 1 dans les cases où les élèves doivent faire des croix, puis calculez le nombre en faisant le produit des entêtes de colonnes dont les cases sont marquées.

      Reste encore à les multiplier par des nombres premiers « pas trop grands » mais plus grands que 10 choisis aléatoirement dans une liste.

      Plus qu’à colorier les « 1 » des cases en blanc avant d’imprimer les problèmes de vos élèves, et voilà !

      mise à jour : ai fait une première version ici