La conjecture de sierpinski

Soyez le premier à donner votre avis sur cette source.

Vue 4 372 fois - Téléchargée 101 fois

Description

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 / Exemple :


#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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_juju12
Messages postés
968
Date d'inscription
samedi 3 avril 2004
Statut
Membre
Dernière intervention
4 mars 2010
4 -
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.
pgl10
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1 -
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.
pgl10
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1 -
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.
pgl10
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1 -
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 ?
pgl10
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1 -
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

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.