Lucas Willems

LUCAS WILLEMS

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

English

Project Euler 21 : solution Python

Article

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

Evaluate the sum of all the amicable numbers under 10000.

Compréhension du problème

Reformulons le problème : il nous faut trouver la somme de tous les nombres amicaux inférieurs à 10000. Pour résoudre ce problème, le plus simple, je pense, est de tester, pour tous les nombres \(n\) inférieurs à 1, si, lorsque \(m = d(n)\) (la fonction \(d(n)\) étant la somme des diviseurs de \(n\)), \(n = d(m)\).

Le programme

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

def divisors(nb, extremum = False):
    divisors = []
    inf = 1 if extremum else 2
    for i in range(inf, int(nb**0.5)+1):
        q, r = divmod(nb, i)
        if r == 0:
            if q >= i:
                divisors.append(i)
                if q > i:
                    divisors.append(nb//i)
    return divisors
#La fonction d prend en paramètre un nombre et retourne la somme des
#diviseurs de n, n étant exclu
def d(nb):
    return 1 + sum(divisors(nb))
resultat = 0
for a in range(1, 10000):
    b = d(a)
    if d(b) == a and a != b:
        resultat += a
print(resultat)

Le programme étant relativement simple, je n'ai pas d'explications supplémentaires à donner si ce n'est que la fonction "divisors" est explicité dans cet article.

Le résultat

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

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.