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 :

• lister tous les nombres abondants inférieurs à 28124
• trouver toutes les sommes différentes de 2 nombres abondants possibles
• en déduire les nombres qui ne peuvent pas être écrits comme la somme de 2 nombres abondants
• faire la somme de ces nombres

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.