Voici un résumé de l'énoncé du problème 29 "Distinct powers" du Project Euler (traduction complète en français ici) :

How many distinct terms are in the sequence generated by \(a^b\) for \(2 \leq a \leq 100\) and \(2 \leq b \leq 100\) ?

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de termes distincts pouvant être générés par \(a^b\) avec \(2 \leq a \leq 100\) et \(2 \leq b \leq 100\). Pour résoudre ce problème, la façon la plus simple, à mon sens, consiste à :

• mettre dans une liste, sans vérifier s'ils ont déjà été obtenus une 1ère fois, tous les termes pouvant être générés par \(a^b\) en faisant varier a et b de 2 à 100
• supprimer tous les doublons de cette liste
• regarder le nombre de terme qu'il reste dans notre liste

Même si cette méthode est relativement simple à mettre en place et assez rapide à exécuter, elle n'est sûrement pas optimale.

Le programme

Voici le programme Python que nous pouvons utiliser pour résoudre ce problème :

powers = []
for a in range(2, 101):
    for b in range(2, 101):
        powers.append(a**b)
#Suppresion de tous les doublons de la liste powers
resultat = len(list(set(powers)))
print(resultat)

Le résultat

La réponse à ce problème est 9183.