Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 30 : solution Python

Article

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

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Compréhension du problème

Reformulons le problème : il nous faut trouver la somme de tous les nombres qui peuvent être écrits comme la somme de leurs chiffres à la puissance 5.

Pour résoudre ce problème, nous pouvons procéder de la manière suivante : tester, pour tous les nombres inférieurs à une certaine borne (une limite est obligatoire sinon le programme ne se finirait jamais), si ces nombres sont égaux à la somme de leurs chiffres à la puissance 5. Il nous faut donc trouver la valeur de cette borne, et celle-ci correspond tout simplement au nombre à partir du quel tous les nombres supérieurs sont forcément plus grands que la somme de leurs chiffres à la puissance 5. Ce nombre est :

$$9^5 + 9^5 + 9^5+ 9^5+9^5+9^5 = 6 \times 9^5 = 354294$$

Cela signifie donc que pour obtenir le nombre 354294, il nous faut faire la somme des chiffres à la puissance 5 de 999999. On peut donc en déduire que pour obtenir des nombres supérieurs à 354294, il nous faudra faire la somme des chiffres à la puissance de 5 de nombres à 7 chiffres et donc que tous les nombres supérieurs à 354294 ne peuvent pas être écrits comme la somme de leurs chiffres à la puissance 5.

Nous savons comment procéder et jusqu'où et pouvons donc passer au programme.

Le programme

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

def sum_digits_fifth_powers(nb):
    sum = 0
    for i in str(nb):
        sum += int(i)**5
    return sum
resultat = 0
for i in range(2, 354295):
    if i == sum_digits_fifth_powers(i):
        resultat += i
print(resultat)

Le résultat

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

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.