begin process at 2012 05 27 14:48:17
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths & Algorithmes

 > LA CONJECTURE DE SIERPINSKI

LA CONJECTURE DE SIERPINSKI


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :arithmétique, mode console, grands nombres, écriture accentuée, conjecture Sierpinski Niveau :Débutant Date de création :21/11/2009 Date de mise à jour :06/12/2009 22:07:28 Vu / téléchargé :2 877 / 53

Auteur : pgl10

Ecrire un message privé
Site perso
Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
La conjecture de Sierpinski dit que :
5/d = 1/i +1/j +1/k
est toujours possible en nombre entiers. Cette conjecture n'est pas démontrée. Mais on ne connait aucun contre-exemple. Le programme présenté ici permet de vérifier cette conjecture pour la valeur donnée du dénominateur d, en utilisant pour la décomposition des nombres entiers compris entre 1 et une limite donnée. Avec la méthode utilisée ici, il est nécessaire d'employer des entiers sur 64 bits pour autoriser une limite supérieure à 950. Si on choisit une limite de 1000 le plus grand dénominateur possible sera de 1665. Toutefois 1664 et bien d'autres entiers plus petits n'ont pas de décomposition avec les entiers de l'intervalle 1 à 1000, mais ils en ont bien sûr avec un intervalle plus grand ! Parmi ces derniers c'est 73 le plus petit. Et bien sûr, beaucoup d'autres entiers plus petits que 1665 admettent une ou plusieurs décompositions dans cet intervalle. Ce programme permet de les calculer.

Source

  • #include <stdio.h>
  • #include <stdlib.h>
  • int main (){
  • __int64 maxint=9223372036854775807,ll,ln,ld,li,lj,lk;
  • int l,n,d,i,j,k,i1,im,jm,nd;
  • n=5;
  • printf("\n Conjecture de Sierpinski \n");
  • printf("\n En utilisant pour la d\202composition des nombres limit\x82s \x85 : ");
  • scanf("%d",&l);
  • ll=(__int64)l;
  • ln=(__int64)n;
  • if(ln*ll>maxint/(ll*ll)){
  • printf("\n La limite est trop grande !\n\n");
  • system("pause");
  • return(1);
  • }
  • printf("\n Donnez le d\x82nominateur : ");
  • scanf("%d",&d);
  • if(!(d>1)) {
  • printf("\n Il faut un d\x82nominateur > 1 !\n\n");
  • system("pause");
  • return(1);
  • }
  • ld=(__int64)d; nd=0;
  • i1=d/n; if(i1<1)i1=1;
  • im=1+(3*d-1)/n;
  • for(i=i1;i<=im;i++) {
  • li=(__int64)i;
  • if(n*i<=d) jm=l; else jm=2*d*i/(n*i-d);
  • if(jm>l) jm=l;
  • for(j=i;j<=jm;j++){
  • lj=(__int64)j;
  • if(ln*li*lj!=ld*(li+lj))lk=ld*li*lj/(ln*li*lj-ld*(li+lj));
  • if(ln*li*lj*lk==ld*(li*lj+lj*lk+lk*li)){
  • k=(int)lk;
  • if(k>=j&&k<=l){
  • printf("\n %d/%d = 1/%d + 1/%d + 1/%d",n,d,i,j,k);
  • nd=nd+1;
  • }
  • }
  • }
  • }
  • printf("\n\n Avec les entiers de [1,%d] %d/%d a %d ",l,n,d,nd);
  • if(nd<2) printf("d\202composition\n\n");
  • else printf("d\202compositions diff\x82rentes\n\n");
  • system("pause");
  • return(0);
  • }
#include <stdio.h>
#include <stdlib.h>
int main (){
__int64 maxint=9223372036854775807,ll,ln,ld,li,lj,lk;
int l,n,d,i,j,k,i1,im,jm,nd;
n=5;
printf("\n Conjecture de Sierpinski \n");
printf("\n En utilisant pour la d\202composition des nombres limit\x82s \x85 : ");
scanf("%d",&l);
ll=(__int64)l;
ln=(__int64)n;
if(ln*ll>maxint/(ll*ll)){
      printf("\n La limite est trop grande !\n\n"); 
      system("pause"); 
      return(1);
}
printf("\n Donnez le d\x82nominateur : ");
scanf("%d",&d);
if(!(d>1)) {
      printf("\n Il faut un d\x82nominateur > 1 !\n\n"); 
      system("pause"); 
      return(1);
}
ld=(__int64)d; nd=0;
i1=d/n; if(i1<1)i1=1;
im=1+(3*d-1)/n;
for(i=i1;i<=im;i++) {
      li=(__int64)i;
      if(n*i<=d) jm=l; else jm=2*d*i/(n*i-d); 
      if(jm>l) jm=l;
      for(j=i;j<=jm;j++){
            lj=(__int64)j;
            if(ln*li*lj!=ld*(li+lj))lk=ld*li*lj/(ln*li*lj-ld*(li+lj));
            if(ln*li*lj*lk==ld*(li*lj+lj*lk+lk*li)){
                  k=(int)lk;
                  if(k>=j&&k<=l){
                        printf("\n %d/%d = 1/%d + 1/%d + 1/%d",n,d,i,j,k); 
                        nd=nd+1;
                  }
            }
      }
}
printf("\n\n Avec les entiers de [1,%d] %d/%d a %d ",l,n,d,nd); 
if(nd<2) printf("d\202composition\n\n"); 
else printf("d\202compositions diff\x82rentes\n\n"); 
system("pause");
return(0);
}

 Conclusion

Vous pouvez faire des vérifications pour divers intervalles et divers dénominateurs.
Le plus grand intervalle utilisable ici est : [1,1226421].
Le nombre de décompositions obtenues est très variable.
Ici, 5/180 a 537 décompositions de Sierpinski et 5/181 en a 5 !
Toute remarque, amélioration ou signalement d'erreur sont bienvenus.

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

22 novembre 2009 13:30:51 :
Prise en compte des remarques de JUJU12.
22 novembre 2009 17:46:48 :
Un complément d'explication.
30 novembre 2009 09:02:49 :
Ajout du nombre de décompositions obtenues
30 novembre 2009 09:19:05 :
Petite correction de présentation
06 décembre 2009 22:07:29 :
Limitation de la boucle j pour aller plus vite

 Sources du même auteur

Source avec Zip Source avec une capture UNE LISTE HÉTÉROGÈNE DOUBLEMENT CHAINÉE
Source avec Zip Source avec une capture POUR AFFICHER LES CARACTÈRES ACCENTUÉS SOUS WINDOWS EN MODE ...
Source avec Zip Source avec une capture CONVHTML : UN UTILITAIRE DE CONVERSION POUR FICHIERS HTML
Source avec Zip Source avec une capture AFFIMOFF : UNE VISIONNEUSE 3D AVEC PARAMÉTRISATION ET TEXTUR...
Source avec Zip Source avec une capture CRIBLE D'ERATOSTHÈNE OPTIMISÉ

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel

 Sources en rapport avec celle ci

Source avec Zip EVALUATEUR D'EXPRESSION ARITHMÉTIQUE par matrx180vTitanium
Source avec Zip Source avec une capture POUR AFFICHER LES CARACTÈRES ACCENTUÉS SOUS WINDOWS EN MODE ... par pgl10
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture EVALUATEUR_EXPRESSION_ARITHMETIQUE par Donald180v
Source avec Zip Source avec une capture CONVERSION EN FRACTION ÉGYPTIENNE par pgl10

Commentaires et avis

Commentaire de juju12 le 22/11/2009 00:20:18

Bonjour;

if(3*d/n*n==3*d) im=3*d/n; else im=1+3*d/n;
peut être remplacé par simplement :
im=1+(3*d-1)/n;

D'un point de vue algorithmique, il n'est pas nécessaire de faire la boucle sur k; il suffirait par exemple de le calculer à partir de i et j
5ijk=n(ij+ik+jk) => k=(nij)/(5ij-n(i+j)),
puis regarder s'il y a égalité 5ijk==n(ij+ik+jk).
Ca diminuera le temps de calcul d'un facteur assez élevé! (bien que pour des nombres aussi petits je suppose que le calcul ne prend qu'un instant, mais bon, pour le principe, et si tu veux par la suite travailler avec des nombres arbitrairement grands...)


Voilà, c'est pas exhaustif, on peut toujours améliorer... mais bonne continuation.

Commentaire de pgl10 le 22/11/2009 13:33:14

Grand merci à JUJU12 pour ses deux améliorations judicieuses. La deuxième permet effectivement de fortement diminuer le temps de traitement. J'avais déjà limité la boucle sur i. Maintenant la boucle sur k est supprimée. Ce qui permet d'utiliser des intervalles [1,limite] aussi grands que l'on veut.

Commentaire de pgl10 le 23/11/2009 11:59:54

Pour ceux qui le souhaitent il y a aussi une autre méthode :
en effet si : n/d=1/i+1/j+1/k
on a : r=(n*i-d)/(d*i)=(j+k)/(j*k)
connaissant i et j on calcule en (long double) : r
puis k=j/(r*j-1) => OK si k entier.
Ceci pourrait avoir de meilleures limites autorisées.

Commentaire de pgl10 le 07/12/2009 11:53:26

Dans la version actuelle de ce programme,
avec les entiers de [1,1226421]
2477/5 , 2557/5 , 2663/5 et 2999/5
n'ont qu'une seule décomposition.
Ont-ils d'autres décompositions ?
Quels autres nombres n'ont qu'une décomposition ?

Commentaire de pgl10 le 07/12/2009 13:48:09

Comme je ne peux pas corriger, c'est bien sûr
de : 5/2477 , 5/2557 , 5/2663 et 5/2999
dont je voulais parler ci-dessus. Désolé, pgl10

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Comment chercher un opérande central d'une expression arithmétique [ par kadermissoum ] Bonjour; J'ai l'expression arithmétique suivante : S = "((A+B)*(C-(D/E)))";     |-----| |-||---|     |-----| |---------|        PG       PD - Je vou Moyenne arithmétique et casting [ par DONALD3D ] Hello, j'espère que je poste au bon endroit.[^^clinoeil1] J'ai besoin d'une confirmation sur un casting, je ne suis pas certain de m'y prendre corre


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

Photothèque

A découvrir



 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,279 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales