coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 2012
-
24 août 2004 à 15:49
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 2012
-
4 sept. 2004 à 15:34
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 4 sept. 2004 à 15:34
bon, je ne te suis pas mais c'est pas grave, tu dois avoir raison, je vias voir si on peut exploiter ça facilement...
cruchacode
Messages postés11Date d'inscriptionsamedi 14 août 2004StatutMembreDernière intervention22 février 2012 4 sept. 2004 à 15:29
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
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 4 sept. 2004 à 12:55
16 = 2^3 * 2 et 2 = 2^1
voila je crois que comme 3 et 2 sont premiers alros 16 est parfait ...
16 != 2 +8 +4 +1
a moins que je ne me trompe 16 n'a pas d'autres diviseurs donc il n'eest pas parfait pourtant, selon ta technique, il dvrait l'être...
cruchacode
Messages postés11Date d'inscriptionsamedi 14 août 2004StatutMembreDernière intervention22 février 2012 4 sept. 2004 à 12:37
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
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 4 sept. 2004 à 12:32
mais la tu peux ariver a nimporte quel nombre pair...
cruchacode
Messages postés11Date d'inscriptionsamedi 14 août 2004StatutMembreDernière intervention22 février 2012 4 sept. 2004 à 12:29
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
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 4 sept. 2004 à 10:10
tu te trompes 6 n'ets pas un exposant de deux, 28 non plus 496 non plus, et le suivant est vraiment très grand...
il existe des nombres premiers de l'ordre de 2 ^p -1 avec p premier, on es apelle les nombres de mercène, je suposes que tu as confondu avec ça...
cruchacode
Messages postés11Date d'inscriptionsamedi 14 août 2004StatutMembreDernière intervention22 février 2012 4 sept. 2004 à 01:01
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 !!
Katasstrov
Messages postés5Date d'inscriptionsamedi 24 juillet 2004StatutMembreDernière intervention28 août 2004 28 août 2004 à 12:45
Tu as tout à fait raison coucou47 !
Les nombres pairs doivent être retenus et la seconde boucle doit tourner avec un incrément de 1.
En fait, 6 doit être le seul nombre parfait avec des diviseurs premiers (3+2+1).
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 28 août 2004 à 09:41
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
Katasstrov
Messages postés5Date d'inscriptionsamedi 24 juillet 2004StatutMembreDernière intervention28 août 2004 27 août 2004 à 23:53
Il est vrai que la seconde boucle peut s'arrêter à racine carrée du nombre +1.
On peut encore optimiser ce programme en incrémentant la seconde boucle de +2 à partir de 3.
Il est en effet inutile de tester les divisions par les nombres pairs.
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 27 août 2004 à 14:47
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...
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 24 août 2004 à 15:49
ton code est un peu long a exécuter, car : il va chercher jusqu'a nombre/ 2 alors qu'aller jusqu'a la racine du nombre +1 serais bien plus rapide... (vous retiendrez en cas de division, diviseur + nombre / diviseur enfin seulement si nombre / diviseur != nombre...) enfin bref, on peut faire plus rapide ^^
4 sept. 2004 à 15:34
4 sept. 2004 à 15:29
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
4 sept. 2004 à 12:55
voila je crois que comme 3 et 2 sont premiers alros 16 est parfait ...
16 != 2 +8 +4 +1
a moins que je ne me trompe 16 n'a pas d'autres diviseurs donc il n'eest pas parfait pourtant, selon ta technique, il dvrait l'être...
4 sept. 2004 à 12:37
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
4 sept. 2004 à 12:32
4 sept. 2004 à 12:29
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
4 sept. 2004 à 10:10
il existe des nombres premiers de l'ordre de 2 ^p -1 avec p premier, on es apelle les nombres de mercène, je suposes que tu as confondu avec ça...
4 sept. 2004 à 01:01
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 !!
28 août 2004 à 12:45
Les nombres pairs doivent être retenus et la seconde boucle doit tourner avec un incrément de 1.
En fait, 6 doit être le seul nombre parfait avec des diviseurs premiers (3+2+1).
28 août 2004 à 09:41
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
27 août 2004 à 23:53
On peut encore optimiser ce programme en incrémentant la seconde boucle de +2 à partir de 3.
Il est en effet inutile de tester les divisions par les nombres pairs.
27 août 2004 à 14:47
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...
24 août 2004 à 15:49