Python Quizz: Résoudre le problème des puissances de deux

J'avoue bien aimer les énigmes mathématiques et parfois me casser la tête sur les défis mathématiques du journal le Monde. Le suivant m'a laissé assez perplexe : "Une puissance de 2 peut-elle commencer par les quatres chiffres 2000?". La réponse est oui mais la justification théorique n'est pas simple. Plusieurs lecteurs ont trouvé ces puissances à l'aide d'une calculatrice. Comme disait un de mes profs de math, je vous propose de résoudre ce problème par "la méthode bourrin" avec Python comme super-calculatrice. Comment trouver les nombres (inférieurs à 10000) qui mis à la puissance de 2 donnent un résultat qui commence par 2000? La réponse devrait tenir en une seule ligne de code.

Question subsidiaire: Comment afficher ces nombres ainsi que le nombre de chiffres de leur résultat au fil de l'eau. Là vous avez le droit à 4 lignes de code :) ?

La réponse d'ici quelques jours en mise à jour de ce billet. Petit indice la solution "bourrin" est beaucoup plus facile que la solution mathématique pour laquelle je vous laisse vous reporter à l'excellent livre nommé ci-dessus.

Mise à jour: la solution

Utiliser une compréhension de liste

Comme proposé par Goulwen, une compréhension de liste est un moyen très efficace pour trouver les résultats. Voici ma version:

print [x for x in xrange(10000) if str(pow(2, x))[:4]=="2000"]

On trouve ainsi que 3 nombres [2137, 4273, 6409] suivent cette condition.

Si vous n'êtes pas famillier avec les compréhensions de liste. Je vous recommande cet article sur Wikipedia. C'est un moyen d'écrire le code suivant de manière plus concise:

results = []
for x in xrange(10000):
if str(pow(2, x))[:4]=="2000":
results.append(x)
print results

Une compréhension de liste permet de générer une liste depuis des éléments d'une séquence en permettant de filtrer (la partie qui suit le if et qui est optionnelle) et de transformer (la partie qui précède le for: ici on a simplement x qui représente l'élement en cours mais cela pourrait être n'importe quelle expression Python) les éléments. Ce mécanisme permet d'associer 2 fonctions du langage Python map et filter en un seul concept.

Ou encore mieux un générateur

Passons à la question subsidiaire. On pourrait pour afficher les résultats tout simplement boucler sur les éléments de la liste et en afficher la valeur. Mais dans ce cas, avant de pouvoir afficher le 1er résultat, il faut avoir calculer tous les éléments.

Cela vous fait peut-être penser à la différence entre les fonctions range et xrange. range retourne une liste de nombres selon une progression arithmétique: [0, 1, 2, 3] par exemple. xrange retourne lui un générateur qui à chaque fois qu'il est invoqué dans une boucle for va retourner l'élément suivant de cette même progression arithmétique. Le 1er appel retourne 0, puis le second 1, puis 2, puis 3 et termine la boucle via une exception de fin d'itération.

Alors comment utiliser un générateur plutôt qu'une liste de compréhension? La solution est simple puisque la syntaxe utilisée est presque identique. La seule différence, on ne met pas le code entre les [] de la liste mais directement en argument d'une fonction. Pour cette fonction, on affiche les éléments d'une séquence que celle-ci soit d'ailleurs issue de la liste ou du générateur:

def affiche(seq):
for x in seq:
print "2**%d --> %d chiffres" % (x, len(str(pow(2, x))))

Au lieu de passer la liste des résultats, on passe donc simplement le générateur qui permet d'en trouver les éléments.

affiche(x for x in xrange(10000) if str(pow(2, x))[:4]=="2000")

Les résultats sont ainsi affichés au fil de l'eau.

Voilà, merci et bravo à Goulwen pour sa réponse. Une simple remarque, je pense que [:4]==2000 est plus performant que le find('2000')==0 puisqu'il ne teste la valeur qu'en début de chaîne.

Merci aussi à Fabien pour m'avoir recommandé via twitter le site projecteuler qui propose un grand nombre d'énigmes mathématiques à résoudre par la programmation. Voilà de quoi s'amuser