RECHERCHE DES NOMBRES PARFAITS

Commentaire de coucou747 le 27/08/2004 14:47:20 administrateur CS

Bah alors tu refais pas ta source, Personne ne prends ta défense, personne ne donne d'optiomisations ? Y a qqn ? ^^

Bon, tt ça pour te dire que la j'ai un peu plus de temps :
#include <stdio.h>
#define nmax 10000
int main(){           //main est tjrs du type int !!!
unsigned long int n, somme_diviseur, diviseur2, diviseur, a;
for(n=2; n<=nmax; n++){
somme_diviseur=1;
for(diviseur=2; diviseur*diviseur<=n; diviseur++){
if(n%diviseur==0){
diviseur2=n/diviseur;
if (diviseur==diviseur2){
somme_diviseur+=diviseur;
}else{
somme_diviseur+=diviseur+diviseur2;
}
}
}
if (n==somme_diviseur)
printf("nombre parfait : %u\n", n);
}
}

et encore je ne me suis pas fait chier avec math.h...

je suposes que c'ets bcp plus rapide...

Commentaire de coucou747 le 28/08/2004 09:41:20 administrateur CS

sisi c'est utie pour les nombres parfait, c'est pas utile pour les nombres premiers mais pour les parfait, j'insiste !
28 :
1*28
2*14
4*7

voila ces diviseurs et 4 en fait parti, la ok, comme c'ets 4*7 ça ne change rien, mais si ça avait été 4*8 alos ni 4 ni 8 n'auraient étés testé donc aucun ajouté... Donc nombre oublié au ajouté alors qu'il ne fallait pas

Commentaire de cruchacode le 04/09/2004 01:01:55

Entre 1 et 10 000 ... et plus loin encore, tout nombre parfait est un multiple de 2 de la forme 2^k, k premier somme des puissances de 2 de i=0 à n=k... ce qui permet d'éviter bien des calculs... si on dispose d'une minuscule table des nombres premiers... disons jusqu'à 101 par exemple...

P.S. n de la forme ... ==> parfait
Mais je ne connais pas de démonstration de la réciproque... toutefois jusqu'à 100 000 no pb !!

Commentaire de cruchacode le 04/09/2004 12:29:14

6   = 2^1 * 3 et 3 = 2^0 + 2^1
28 = 2^2 * 7 et 7 = 2^0 + 2^1 + 2^2

La démonstration du théorème est relativement simple :

Soit P = 2^n * z, z=Somme(i>=0,i<=n : 2^i), z premier

Somme des diviseurs de P :
avec 2^n ==> Somme(i>=0,i<=n : 2^i)
avec Z ==> z
avec les produits ==> z * Somme(i>=0, i<n : 2^i)

Or z = Somme(i>=0,i<=n : 2^i) = 2^(n+1) -1

Donc au total
(2^(n+1) - 1) (1 + 2^n -1) = P , CQFD

Commentaire de cruchacode le 04/09/2004 12:37:33

Tu peux programmer une recherche des nombres parfaits en utilisant ce thm... tu verras que tu trouve exactement les nombres parfaits et eux seuls...

En réfléchissant un peu tu verras aussi combien ce thm est beau !!
chercher un nombre premier somme des puissances de 2 de 0 à n ==> construire un nombre parfait...

De tels nombres premiers sont plutôt rares... 3 en dessous de 1000 et les choses vont en se raréfiant

Commentaire de cruchacode le 04/09/2004 15:29:15

Sorry, je m'explique plus clairement : ce n'est pas l'exposant de 2 qui est le facteur premier, mais le facteur premier qui est la somme des puissances de 2 de 0 à l'exp max du facteur 2

Exemple :
3 = 2^0 + 2^1, 3 est premier => 2^1 * 3 est parfait
7 = 3 + 2^2, est premier 2^2 * 7 est parfait

Et j'insiste, le nombre premier doit être la somme de 1, 2, ... sans "trous" jusqu'au facteur 2^k

Si tu regardes la démonstration, tu comprendras sans doute prourquoi de tels nombres sont NECESSAIREMENT parfaits...

2 termes dont l'un premier, l'autre une puissance (n) de premier ==> nombre de diviseurs propres = n + n-1 + 1
soit 2 n termes.

Etudions les termes,


Nombre premier = (2^(n+1) -1)
Nombre pair alors choisi    = 2^n

Diviseurs :
Premier
   (2^(n+1) -1)
Puissances de 2 :
   (2^(n+1) -1)
Produits des puissances et du premier :
   (2^(n) -1) * (2^(n+1) -1)
  
...mais on ne doit pas compter 2 fois le premier (2^0 = 1..)  
  
Somme des div
   (2^(n+1) -1) (1 + (2^(n) -1))
   (2^(n+1) -1) * ((2^(n))

La somme des div est donc bien égale au nombre de départ