Nombres parfaits de Nichomacus

Salut tout le monde,

En ce moment, j’apprends le python, et j’utilise pour ça exercism.io, qui propose des exercices pour apprendre le langage au fur et à mesure. Je suis en train de faire un side-exercise, ce qui veut dire que je n’ai pas de review dessus.

Cet exercice, c’est celui des nombres parfaits selon Nicomachus. Un nombre est parfait si la somme de ses facteurs (lui-même excepté) est égal à lui-même (6 = 1 + 2 + 3, et 6 est divisible par 1, 2 et 3). Si cette somme est supérieure, le nombre est alors abondant, si la somme est inférieure alors le nombre est déficient.

Je n’ai pas de problème avec la logique pour le faire, et j’ai très bien réussi. Mon code passe tous les tests, ce qui est plutôt bon signe. Maintenant, le problème c’est que les tests prennent plus de 2 secondes à s’exécuter, pour mon code qui fait 25 lignes. Faut dire que dans les tests, ça passe 2 fois par des valeurs à plus de 30 millions.

Actuellement, mon code passe par une boucle qui teste chaque entier inférieur à la moitié + 1 du nombre à classer pour vérifier le modulo. Si le modulo = 0, alors l’entier est ajouté dans la somme d’Aliquot. Ensuite, la somme est comparée avec le nombre à classer. Je me demandais s’il y avait moyen d’optimiser ce petit code ?

Sur exercism, je peux regarder les autres solutions de la communauté, qui sont parfois des trucs bizarres pour faire le moins de lignes possibles, mais parfois aussi des optimisations de code. C’est cool, mais je préfèrerais idéalement avoir des orientations sur lesquelles chercher, plutôt que les solutions déjà écrites du reste de la communauté

Pour voir la consigne complète et les tests, c’est dispo sur mon Github, parce que je ne suis pas sûr que ce soit accessible sur exercism.io sans inscription. Et pour mon code (aussi dispo sur Github, si jamais) :

def classify(number: int) -> str:
    """Classify the int following the Nicomachus' classification of perfect numbers.
    """
    classification: str = ""
    if number < 1 or int(number) != number:
        raise ValueError("Can't classify this number or value")
    elif number == 1:
        classification = "deficient"
    else:
        aliquot = aliquot_sum(number)
        if aliquot > number:
            classification = "abundant"
        elif aliquot < number:
            classification = "deficient"
        else:
            classification = "perfect"
    return classification


def aliquot_sum(number: int) -> int:
    aliquot: int = 0
    for i in range(1, number // 2 + 1): # Yup, no need to test more, and I needed someone to tell me that...
        if number % i == 0:
            aliquot += i
    return aliquot

C’était redoutablement logique, merci beaucoup Je m’étais demandé si j’avais un truc à faire avec la racine carrée parce que j’avais déjà fait il y a longtemps un exercice sur les nombres premiers, et que ça l’exploitait.

Je suis passé de 2.145s à 0.006s pour les tests, c’est nickel ! J’ai dû tweaker un peu le code pour que ça rentre dedans. Notamment, il y a un cas spécifique, c’est quand la racine d’un nombre est entière. Dans ce cas, la racine est ajoutée 2 fois, par défaut. Je pourrais tester à chaque fois, mais j’ai préféré, pour optimiser, tester après la somme et soustraire la valeur en trop.

def classify(number: int) -> str:
    """Classify the int following the Nicomachus' classification of perfect numbers.
    """
    classification: str = ""
    if number < 1 or int(number) != number:
        raise ValueError("Can't classify this number or value")
    elif number == 1:
        classification = "deficient"
    else:
        aliquot = aliquot_sum(number)
        if aliquot > number:
            classification = "abundant"
        elif aliquot < number:
            classification = "deficient"
        else:
            classification = "perfect"
    return classification


def aliquot_sum(number: int) -> int:
    aliquot: int = 1
    for i in range(2, int(number ** (1 / 2))+1):
        # Let's say number = X * Y. If we find X, then we find Y. So we can add Y to aliquot.
        if number % i == 0:
            aliquot += i
            aliquot += number / i
    if int(number ** (1/2)) == number ** (1/2):
        # If sqrt(number) is an integer, then we added it 2 times. Here, we correct that by subtracting it if necessary.
        aliquot -= number ** (1/2)
    return aliquot

Tu fais tourner ton code que sur un seul nombre ou un intervalle ?

Sur un seul nombre, mais les tests en contiennent plusieurs. Sur un intervalle, tu imaginerais sans doute de faire ça par ordre croissant et de conserver les sommes à chaque fois ?

Nan j’aurais plutôt envie de calculer les nombres premiers

J’y ai réfléchi, mais je ne vois pas bien comment utiliser les nombres premiers, vu que je dois aussi additionner les diviseurs non premiers.

Tu peux diviser successivement par récurrence. Une fois que t’as décomposé ton nombre en produit de facteurs premier, tu peux retrouver tous ses diviseurs en composant les facteurs premiers

Je pense que tu devrais parcourir jusqu’à la racine exclue. Et vérifie ensuite le cas de la racine. Ça me semble plus beau.

Ensuite, la racine étant une opération coûteuse, je pense que tu gagnes à là faire le moins de fois possible.

def aliquot_sum(number: int) -> int:
    aliquot: int = 1
    sqrt_number: int = int(number ** (1 / 2) + 0.5)
    for i in range(2, sqrt_number):
        # Let's say number = X * Y. If we find X, then we find Y. So we can add Y to aliquot.
        if number % i == 0:
            aliquot += i
            aliquot += number // i

    if sqrt_number * sqrt_number == number:
        aliquot += sqrt_number

    return aliquot

Dernier point, on veux savoir si un nombre est abondant, parfait ou déficient. Si un nombre apparaît clairement abondant on a plus vraiment besoin de calculer la somme exacte de ses diviseurs (dès qu’elle est dépassée, le nombre alors le nombre n’est plus parfait). Je ne suis pas sûr qu’on puisse avoir le même raisonnement avec un nombre déficient.

J’ai du mal à voir la notion, va falloir que j’aille récupérer le fond de maths qu’il me reste quelque part au fond de mon cerveau.

Je pense que tu devrais parcourir jusqu’à la racine exclue. Et vérifie ensuite le cas de la racine. Ça me semble plus beau.

Ensuite, la racine étant une opération coûteuse, je pense que tu gagnes à là faire le moins de fois possible.

C’est ce que j’ai testé de base, mais ça pose problème sur 2 valeurs, le 6 et le 8. Leur racine étant de 2 quelque chose, la conversion en int la tronque à 2. Et ça donne un range(2, 2), donc rien du tout, et ça ne m’ajoute ni le 2 ni le 3 (pour la valeur 6) ou le 4 (pour la valeur 8).

C’est vrai, ça implique de rajouter une condition à tester dans la boucle, mais c’est possible. Cependant, ça veut dire que je dois enlever le calcul de la fonction aliquot_sum pour le mettre dans la fonction principale.

Ah oui, avec un ceil c’est peut-être beaucoup plus propre ! Faut que je teste sur mon PC perso, merci

Ah oui, mais du coup ça implique de savoir à l’avance jusqu’où tu vas, parce que sinon je dois tester chaque nombre jusqu’à la racine et voir s’il est premier, non ?

Vu que le nombre premier maximal possible est en racine du plus grand nombre de l’intervalle, tu peux même avoir une estimation imprécise de ton intervalle et majorer brutalement

Si l’entrée est vraiment un intervalle connu, y a pas besoin de nombres premiers, y a une formule close pour la "contribution" d’un diviseur $d$ plus petit que la racine de la borne supérieure de l’intervalle…

C’est quoi la formule ? Parce qu’on peut toujours prendre pour intervalle un unique nombre et je pense pas que ta formule dira quoi que ce soit de plus

Désolé j’avais pas trop lu l’OP, je pensais qu’il fallait calculer la somme des sommes de diviseurs des nombres de l’intervalle (d’où la "formule" en question, qui n’avait rien de bien sorcier)

Pas forcément, tu as plusieurs façons de faire ça en Python.

Tu pourrais par exemple ajouter un paramètre optionnel maximum à ta fonction pour t’arrêter dès que tu as dépassé ce maximum.
La fonction remplirait toujours son rôle initial mais te permettrait cette optimisation dans ton cas d’utilisation.

J’ai fait la modif proposée par @ache, qui est effectivement beaucoup plus propre, merci

En fait j’avais pensé naturellement à faire un if avec un return abundant dans la boucle. Mais sinon, je peux modifier la boucle comme ça :

    for i in range(2, ceil(number ** (1 / 2))):
        if number % i == 0:
            aliquot += i
            aliquot += number / i
            if aliquot > number:
                return aliquot

Ou alors il faut que je passe d’une boucle for à une boucle while. Mais du coup, ça implique de faire le test à chaque tour de boucle, je sais pas si c’est vraiment plus optimisé, sachant qu’en regardant les valeurs de la somme d’aliquot ne montent pas tant que ça plus haut que la valeur à classifier.