Vous croyiez tout savoir des entiers, et notamment de leurs diviseurs. Par exemple, les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12 ; ses diviseurs stricts sont 1, 2, 3, 4 et 6 (mais pas 12). On notera S(n) la fonction somme des diviseurs stricts de n. Ainsi, S(12) = 1 + 2 + 3 + 4 + 6 = 16.

Mais connaissez-vous les entiers copains ?

Deux entiers n et m sont copains (ou amiables) si S(n) = m et S(m) = n. Dans cette définition, les entiers n et m peuvent éventuellement être égaux. Par exemple, 6 est copain avec 6 car les diviseurs stricts de 6 sont 1, 2 et 3, dont la somme fait bien 6 (S(6) = 6). Un autre couple d'entiers copains célèbre est (220, 284). En effet :

S(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 et S(284) = 1 + 2 + 4 + 71 + 142 = 220.

Par contre, 10 et 40 ne sont pas copains car S(10) = 1 + 2 + 5 = 8 (différent de 40) et
S(40) = 1 + 2 + 4 + 5 + 8 + 10 + 20 = 50 (différent de 10).

Imaginons maintenant que l'on veuille trouver des couples d'entiers copains. On dispose pour cela d'un ordinateur, avec un logiciel pour faire des calculs automatiquement. 

Un simple langage de programmation peut faire l'affaire.

On accumule…

Avant de débuter la recherche de tels couples, il nous faut un outil intermédiaire qui est une fonction, prenant en entrée un entier positif et retournant la somme de ses diviseurs stricts. Mais comment savoir si un entier i divise n ? Il suffit d'utiliser l'opérateur mod (disponible, sous une forme ou une autre, dans de nombreux langages) qui donne le reste de la division euclidienne de n par i. Par exemple, la division euclidienne de 20 par 7 donne 20 = 27 + 6. Ici, 6 est le reste et comme il est non nul, 7 ne divise pas 20. Par contre, 4 divise 20 car 20 = 45 + 0.

Pour obtenir la somme des diviseurs stricts de n, la première idée toute simple est de faire la chose suivante. Initialiser une variable Somme à 0 (c'est ce que l'on nomme un accumulateur). Ensuite, faire une boucle for pour faire varier i de 1 à n – 1. Pour chacune de ces valeurs de i, si i divise n (si n mod i = 0), alors accumuler i dans Somme. À la fin, la variable Somme contient ce qui est demandé (voir en encadré).

Prenons un exemple numérique, n = 100. La boucle va donner à i les valeurs successives de 1 à 99. Mais une petite seconde de réflexion permet de voir qu'il n'y a aucun diviseur de 100 entre 51 et 99. De manière générale, au delà de n / 2, il n'y a plus de diviseur strict de n. Il suffit alors de stopper la boucle for à n / 2 au lieu de n – 1. Mais peut-on la stopper avant ? Réfléchissez-y quelques secondes avant de lire la suite…

Pour n = 100, si i ne va pas jusqu'à 50, le programme ne trouve pas la valeur 50, qui est un diviseur de 100. Pourtant, on peut s'arrêter bien avant n / 2 avec un peu d'astuce. Comment donc s'arrêter avant 50, sans oublier le diviseur 50 ? Examinons les choses : 100 = 50  2. Lorsque 2 est considéré, c'est bien un diviseur de 100, on obtient en réalité non pas un seul mais deux diviseurs de 100, à savoir 2 et 50. De façon générale, si i divise n, il existe un entier q tel que n = iq + 0. Ainsi, i et q sont deux diviseurs de n. Ils peuvent donc être ajoutés tous les deux dans l'accumulateur (Somme := Somme + i + n/i) !

En faisant cela, ne risque-t-on pas d'oublier des diviseurs ? Si n = ixq, alors forcément un seul de ces deux diviseurs vaut au plus  \( \sqrt {{n} }\) (car si i > \( \sqrt {{n} }\)   et q > \( \sqrt {{n} }\) , alors iq > n et si i < \( \sqrt {{n} }\)  et q <  \( \sqrt {{n} }\)  alors iq < n). C'est ce diviseur i ≤  \( \sqrt {{n} }\)  que va permettre de trouver la boucle for.  L'autre, n / i ≥  \( \sqrt {{n} }\) , sera simplement ajouté dans l'accumulateur.

Avec cette modification, il faut cependant faire attention à deux choses. Premièrement, lorsque i = 1, il faut ajouter 1 seulement (et pas n / 1 = n car seuls les diviseurs stricts de n comptent). Pour cela, il suffit d'initialiser l'accumulateur à 1 (Somme :=1) au lieu de 0 avant de lancer la boucle for à partir de 2 au lieu de 1 (1 divise tout entier, mettons-le directement dans l'accumulateur !). Deuxièmement, si n est un carré parfait (par exemple n = 100), alors n = m² (comme 100 = 10²), et m est ajouté deux fois dans l'accumulateur (à la fois m et n / m = m sont ajoutés).
Ce problème peut être facilement résolu en supprimant   \( \sqrt {{n} }\) = m de l'accumulateur après la boucle for si n = m².

Maintenant, la boucle for de recherche des diviseurs i de n va jusqu'à  \( \sqrt {{n} }\)  seulement, et plus jusqu'à n – 1, ce qui est beaucoup plus économique en termes de temps de calcul de S(n). Par exemple, si n = 100 000, alors n / 2 = 50 000 alors que  \( \sqrt {{n} }\)  vaut environ 316,2.

On n'oublie pas les copains

On a construit une fonction qui prend en entrée un entier n (strictement positif) et calcule S(n) de manière efficace. Mais notre problématique est de générer et d'afficher des couples (n, m) d'entiers copains. Comment faire ? Tout d'abord, pour éviter de générer plusieurs fois le même couple (le couple (220, 284) ne doit pas apparaître une seconde fois sous la forme (284, 220)), fixons la règle que le premier membre n du couple (n, m) doit être inférieur ou égal au second : n ≤ m. Il faut ensuite se fixer une limite globale de recherche : la valeur de n ne doit pas dépasser un entier N_MAX, une valeur fixée à l'avance, par exemple 1 000. Autre contrainte : on souhaite afficher tous les couples de copains avec n ≤ N_MAX. Hors de question d'en oublier.

Un programme se dessine : n va varier de 1 à N_MAX grâce à une boucle for et si un copain m de n est trouvé, le couple (n, m) ne sera affichée que si n ≤ m. Cela permet d'avoir les couples en un seul exemplaire et de tous les trouver (pour 1 ≤ n ≤ N_MAX). Mais dans ce beau schéma, il reste une question d'importance : toutes les valeurs possibles de n sont bien prises une à une grâce à une boucle for mais comment trouver m, un copain de n (sachant que n peut ne pas avoir de copain) ?

Peut-être que la solution vous est venue très rapidement. Les étudiants débutant la programmation assis devant un ordinateur, prêts à programmer, ont tendance à partir dans de mauvaises directions, sans prendre la peine de réfléchir. Dans la plupart des cas, leur reflexe est de faire une boucle for pour faire varier n de 1 à N_MAX (ce qui est correct) et, à l'intérieur de cette première boucle, de faire une deuxième boucle for pour faire varier m de 1 à… une valeur qu'ils n'arrivent pas très clairement à identifier : certains essaient n, d'autres N_MAX voire N_MAX². Bref, ils ne savent pas trop où chercher m, ils font donc une boucle for « un peu au hasard ». Cela donne des programmes qui produisent des résultats, justes jusqu'à un certain point, mais très lents. Pourquoi m devrait-il se trouver entre 1 et n ou entre 1 et N_MAX ? Ne peut-on pas le trouver plus efficacement ?

Bien sûr que si, il suffit pour cela de relire la définition : n et m sont copains si n = S(m) et m = S(n). Ainsi, si n a un copain m, alors m = S(n), c'est la définition ! L'entier n peut ne pas avoir de copain, mais s'il en a un, il n'en a qu'un et c'est nécessairement S(n), inutile de le chercher partout désespérément. Ainsi, 220 n'a qu'un seul copain, qui est S(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284. Cela nous donne un programme dont la forme schématique est la suivante :

For n from 1 to N_MAX do

m :=S(n) ; /* Calculer la somme des diviseurs stricts de n */

If n ≤ m then /* Test pour éviter de générer plusieurs fois le même couple */

If n = S(m) then /* Par construction, m = S(n), il suffit de vérifier que n = S(m) */

Afficher(n, m) ; /* Dans ce cas, n et m sont copains. Afficher la bonne nouvelle */

end if ;

end if ;

end do ;

Voici les valeurs affichées en prenant N_MAX = 8 500 :

(6, 6), (28, 28), (220, 284), (496, 496), (1 184, 1 210), (2 620, 2 924), (5 020, 5 564), (6 232, 6 368), (8 128, 8 128).

L'informatique comme outil 

On le constate, l'informatique peut aider les mathématiciens à « se faire une idée » sur un problème grâce à des outils automatiques. Dans cette expérience, un algorithme a pu générer tous les couples de nombres copains jusqu'à une certaine borne fixée à l'avance. L'ordinateur est alors utilisé comme un « cahier de brouillon » grâce auquel il est possible de faire de longs calculs, fastidieux à faire à la main. Certains outils informatiques peuvent aussi aider à résoudre (de manière approchée) des équations que personne ne sait résoudre de manière théorique.

Tout cela est bien intéressant, mais lors de la création d'un logiciel faisant ces tâches, il faut s'assurer :

• qu'il fait exactement que l'on veut qu'il fasse, pas plus, pas moins, et

• qu'il le fait de manière efficace.

Ces deux points sont en eux-mêmes des enjeux fondamentaux de l'informatique : comment prouver un logiciel (preuves de programmes) et comment optimiser un logiciel. Deux domaines de recherche actuels.

À ce jour toutes les réponses ne sont pas connues !