LISTES DES NOMBRES PARFAITS INFERIEURES À N

Commentaire de dubstructor le 22/01/2010 05:30:12

Bonsoir ,

// tous les nbs parfaits connus sont pairs.

Pas faux, mais il n'est pas prouvé qu'un nombre parfait ne puisse pas être impair.

Sinon l'implé de PGL10 est propre, en tout cas plus que celle de Trezeguet qui n'a pas vu qu'il suffisait d'aller jusqu'à la racine du nombre testé, en sachant que pour tout diviseur d trouvé, on peut directement ajouter un autre diviseur d' = n/d .
De plus si la somme dépasse notre nombre, inutile de poursuivre !

if(somme>nb) break;

Accessoirement pour Trezeguet qui nous demandait des conseils d'optimisation :

#  r=j%i;
#
# if(r==0)

ce genre de complication ne sert à rien si on ne se sert pas de j%i par la suite (auquel cas, il serait plus utile de le stocker ; mais ici on peut faire l'économie d'une affectation, directement suivie d'une extraction, à chaque itération).

Enfin, on a quelques résultats intéressants sur les nombres parfaits PAIRS (qui n'exclut en aucun cas l'existence possible de parfaits impairs, seulement ça n'apprend rien sur eux) :
soit p un entier tel que 2^p-1 soit premier (2^p-1 est alors appelé le p-ième nombre de Mersenne, noté Mp), alors [2^(p-1)]*[2^p-1] est parfait - évidemment pair -, et réciproquement (ie, TOUS les nombres parfaits pairs s'écrivent [2^(p-1)]*[2^p-1] avec p un entier tel que 2^p-1 est premier).

Un tel nombre p est nécessairement premier (mais ça ne suffit pas : par exemple 2^11-1=89*23).

Pour savoir si 2^p-1 est premier, il faut donc déjà obligatoirement avoir p premier, et un autre résultat dit que les diviseurs potentiels de 2^p-1 sont à chercher parmi les nombres de la forme 2*k*p+1. On peut donc avancer dans les tests par sauts de 2p.

On peut aussi utiliser l'algorithme suivant (test de Lucas-Lehmer) :

2^p-1 est-il premier ?
Si p n'est pas premier : non.
Si p est premier : construire la suite définie par S(1)=4 et S(n+1)=S(n)^2-2 jusqu'à obtenir S(p-1) ; tester alors si S(p-1) est divisible par 2^p-1. Oui : 2^p-1 est premier ; non : il ne l'est pas.

(attention à ne pas appliquer l'algorithme tel quel, les calculs seraient énormes ! il faut calculer modulo 2^p-1).

Voilà avec tout ça on peut arriver à faire quelque chose ; si par exemple on veut savoir si un nombre donné est parfait :
- si il est impair, on n'a aujourd'hui pas d'autre solution que l'algorithme "naïf" ;
- si il est pair : est-il de la forme 2^(p-1)*(2^p-1), c'est-à-dire s'écrit-il en binaire :
1111.....1111000......00000
où, en numérotant à partir de 0 (LSB), on n'a que des "1" de la position p-1 à 2p-2 ?
       - si oui : le nombre p ainsi obtenu est-il premier ?
                 - si oui : tester si 2^p-1 = 11111...11111 (avec p "1" binaires) est
                   premier.
       - dans tous les autres cas, il n'est pas parfait.

Si on veut énumérer les nombres parfaits PAIRS, la méthode est un peu différente :
- énumérer les nombres premiers p.
- pour chaque p, tester si 2^p-1 est premier.
- si oui : (2^p-1)*(2^(p-1)) est le n-ème nombre parfait pair.

Dans le cas de la première méthode, on pourrait donc avoir l'implémentation suivante, en supposant un type d'entiers de taille illimité que j'appelle huge_int, avec les opérations usuelles définies pour ce type :

int main()
{
     huge_int nombre ;
     do {
           cout << "Nombre pair à tester ? " << endl ;
           cin >> nombre ; //seul mode de saisie envisageable, avec surcharge correcte de >>
     } while(nombre<=0 || nombre&1) ;
     huge_int temp=nombre ;
     long int p=-1; //sert à compter les bits de "nombre", donc un long int devrait //suffire, un nombre même de taille non limitée par son type ne peut dépasser l'espace mémoire
     int flag=0 ;
     do {
           flag += temp&1 ;
           temp >>= 1 ;
           p++ ;
     } while (!flag) ; //à ce niveau p donne la position du premier 1 rencontré,
                       //et "temp" se termine par un 1.
                       //on cherche alors à déterminer si "temp" n'est composé que de uns.
                       //on peut vérifier que dans ce cas, en faisant la somme bit à bit avec
                       //son augmenté de un, on obtient 0 : par exemple,
                       //  1111 & 10000 = 0, alors que c'est faux pour les autres nombres.
     if(temp&(temp+1) || isPrime(p+1)) {
           cout << "\nNombre non parfait !\n" ;
           getch() ;
           return 0 ;
     } //isPrime est un test de primalité quelconque : méthode naïve (crible), probabiliste
       //(type Fermat) etc ..., non développé ici
     long int q=-1 ;
     huge_int temp2=temp+1 ; //la valeur que temp a ici servira plus bas
     while(1)
     {
          if(!(temp2&1)) {
               q++ ; temp2 >>= 1 ;
          } else break ;
     } //q est le nombre de 1 restants, diminué de 1.
     if(p!=q) {
           cout << "\nNombre non parfait !\n" ;
           getch() ;
           return 0 ;
     }
     //ici on est sûr que le nombre a la bonne forme.
     //il s'agit donc maintenant de tester la primalité de 1111...11111 = temp .
     //la méthode est développée puisqu'il existe des tests spécifiques à ce type de nombre:
     //test de Lucas-Lehmer.
     p++ ;
     huge_int s=4 ;
     long int i ;
     for(i=2;i<=p-1;i++)
           s=(((s%temp)*(s%temp))-2)%temp ;
     if(s==0) //pas besoin de refaire un modulo pour tester la divisibilité par temp
          cout << "\nCe nombre est parfait !" ;
     else cout << "\nNombre non parfait ." ;
     getch() ;
     return 0 ;
}