Lucas Willems

LUCAS WILLEMS

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

English

Project Euler 23 : solution Python

Article

Voici un résumé de l'énoncé du problème 23 "Non-abundant sums" du Project Euler (traduction complète en français ici) :

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Compréhension du problème

Reformulons le problème : il nous faut trouver la somme de tous les entiers positifs \(n\) qui ne peuvent pas être écrits comme la somme de 2 nombres abondants. Grâce à l'énoncé, nous savons que \(n < 28124\). Pour résoudre ce problème, la manière la plus simple de procéder est la suivante :

Notez que pour obtenir la somme des nombres ne pouvant pas être écrits comme la somme de 2 nombres abondants, nous n'avons, en réalité, pas besoin de connaître ces nombres, il nous suffit juste de faire la différence entre la somme de tous les nombres entiers inférieurs à 28124 et la somme de tous les nombres inférieurs à 28124 pouvant être écrits comme la somme de 2 nombres abondants.

Le programme

Voici 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
def is_abundant(n): return sum(divisors(n))+1 > n
#Génération d'une liste contenant tous les nombres abondants #inférieurs à 28124 abundants = [i for i in range(2, 28124) if is_abundant(i)] sommes = {} #Génération de toutes les sommes possibles de 2 nombres abondants for i in range(len(abundants)): for j in range(i, len(abundants)): somme = abundants[i] + abundants[j] if somme > 28123: break sommes[somme] = 1 #Différence entre la somme de tous les nombres et la somme #de toutes les sommes de 2 nombres abondants resultat = (28123*28124)//2 - sum(sommes.keys()) print(resultat)

Vous remarquerez que les sommes sont écrites dans un dictionnaire, ce qui permet de créer un index égal à la somme et donc de ne pas avoir besoin de supprimer les sommes en double à la fin, avant de passer à la somme de toutes les sommes. Notez aussi que les fonctions \(\text{is_abundant}\) et \(\text{divisors}\) sont explicitées dans cet article.

Le résultat

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

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.