• Si on prenait L = p+1, p premier, on serait alors obligé de tester tous les antécédents N impairs possibles jusqu’à N = p². C’est le cas le plus terrible. En effet, ici, si on néglige le terme 1, N ~ L². Ou, dit autrement, ce sont les carrés de nombres premiers qui nous obligent à tester les antécédents jusqu’à L². Dans notre programme très performant où nous ne testerons les antécédents N que jusqu’à L3/2/2.5, il va donc nous falloir prendre des précautions pour ne pas oublier des antécédents de ce type. On traite les nombres « oubliés » à part, ce qui ne demande pas trop de temps de calcul.
• D’autres nombres sont gênants : Si L est de la forme 1+p+p², il nous faut tester Tous les antécédents N impairs jusqu’à N = p3. Ici, si on néglige les termes de plus bas degré, N ~ L3/2. Ou, dit autrement, ce sont les cubes de nombres premiers qui nous obligent à tester les antécédents jusqu’à N = L3/2. Certains antécédents de ce type peuvent donc être oubliés dans notre programme où l’on ne teste que jusqu’à L3/2/2.5. Là aussi, on traite les nombres « oubliés » à part, ce qui ne demande pas trop de temps de calcul. Pour ce qui est des nombres N du type pα, avec α > 3, il n’y a pas de problème. En effet, si N = pα, la somme des ses diviseurs est 1+p+p2+…+pα-1. Donc si L est de cette forme, on a N ~ Lα/(α-1), et α/(α-1) < 3/2 quel que soit α > 3. Ces antécédents ont donc tous été déjà testés si on est allé jusqu’à L3/2/2.5, à condition toutefois de prendre L > 244 pour être certain de ne pas avoir d’ennuis avec les puissances quatrièmes de nombres premiers (par exemple si L = 100 < 244, on a L3/2/2.5 = 400 < L4/3 ≈ 464, ce qui pose problème ! Si L > 244, L3/2/2.5 > L4/3).
• Soit N = pq et donc n = σ’(N) = 1+p+q. On traitera tous ces cas à part, car pour trouver les antécédents de cette forme, il suffit de connaître les G(n-1) pour tous les n-1 strictement inférieurs à L. Je rappelle que ici G(n-1) est le nombre de manières différentes d’écrire n-1 comme somme de deux nombres premiers distincts différents de 2. Les N de cette forme si nous ne les traitions pas à part nous obligeraient à tester les N impairs entre 1 et 0.25L². En effet, si L était la somme de deux nombres premiers jumeaux p et q très grands (on a alors l’ordre de grandeur de L qui est 2p égal à p+q à 2 unités près), l’ordre de grandeur de N serait alors le produit pq ≈ p², soit (L/2)² = L²/4. Traiter ainsi les antécédents de cette forme est très efficace. On remplace des décompositions en nombres premiers par de simples tests de primalité !
• Soit N est d’une autre forme que les précédentes : N = pqr,
avec p, q et r premiers distincts est un cas encore bien plus favorable qui ne nous intéresse malheureusement pas
car il y a un cas intermédiaire qui l’est moins, c’est le cas des N de la forme N = pq² que nous allons décortiquer ci-dessous.
Le cas N = pqr est plus favorable que le cas N = pq², car σ’(pqr) = 1+p+q+r+pq+pr+qr (forme(1)), qui est plus grand relativement à pqr que ne l’est σ’(pq²)=1+p+q+pq+q² (forme(2)) relativement à pq².
Donc pour n donné : si n est de la forme (1), son plus grand antécédent N sera plus petit par rapport à lui que si n est de la forme (2).
Toutes les autres formes de N sont encore plus favorables !
Si N = pq², alors σ’(N) = n =1+p+q+pq+q². Or p = N/q², d’où :
n = 1+N/q²+q+N/q+q² (1)
Cette équation (1) est une relation entre n et son antécédent aliquote N (de la forme N = pq²
qui est la « pire » maintenant que nous avons enlevé les cas encore pire) en fonction d’un paramètre q.
On veut ici savoir pour un n donné (qui vaut par exemple L), jusqu’où il faut tester les antécédents N,
sachant que ici, q qui est un nombre premier pourrait à priori prendre toutes les valeurs entières ou mêmes réelles,
cela ne changerait rien : c’est un paramètre.
Notons que si dans le membre de droite de l’équation (1) je négligeais des termes, je rendrais mon cas encore plus pessimiste,
car pour un N fixé, je diminuerais mon n correspondant, ce qui reviendrait au même que si pour un n donné, j’augmentais la taille N de mes antécédents à tester !
Prenons une notation plus familière et posons : n=x ; N=y et q=i, cela donne la relation :
x = 1+y/i²+i+y/i+i² (2)
On reconnaît ici une famille de droites de paramètre i, droites toutes tangentes à une courbe qui est l’enveloppe de ces droites.
Il existe un procédé permettant de trouver l’équation de cette enveloppe. Mais les calculs sont inextricables avec cette famille de droites.
Comme dit un peu plus haut, je peux « négliger » des termes dans mon membre de droite de l’équation :
cela n’aura pour conséquence que de me faire tester un peu plus d’antécédents.
Notons que si je néglige les termes y/i² et i² il me reste 1+i+y/i et je retombe sur l’équation N = 0.25n² dont je parlais plus haut,
mais justement pas intéressante. Cela ne serait pas faux, mais je n’aurais alors rien gagné par rapport à un programme précédent plus simple.
Ne gardons que les termes x = y/i+i² = f(y,i) (E)
Cela nous donne une nouvelle famille de droites plus simple à traiter dont on cherche l’enveloppe. Pour faire cela, on résout :
df(y,i)/di=0 et on en déduit que i=(y/2)1/3 que l’on met dans (E).
On en déduit que :
y = 2x3/2/(33/2)≈(1/2.598)x3/2
Concrètement, nous allons majorer et prendre :
N = (1/2.5)×n3/2
Je signale que cette démarche a été examinée et approuvée par Cédric BARRET qui m’a fourni une démonstration rigoureuse et expliqué pourquoi elle était bonne.
De plus, il est arrivé au même résultat sans négliger aucun terme en faisant à la fin des calculs aux limites à l’aide de Maple, le logiciel de calcul formel.
Voici ci-dessous le programme final écrit avec le logiciel de calcul formel Mathematica, programme qui donne les A(n)
pour tous les n compris entre 1 et 5 000 000 et qui les écrit dans les deux fichiers appelés « valitttop » et « valitttopcolumn » (fichier en colonne plus lisible) :
L1 (b=5 000 000;
L2 Print["OK : Départ !"];
L3 aaa=Date[];Array[a,{b,2}];For[i=1,i≤b,a[i,1]=i;a[i,2]=0;i++;];
L4 ppi=PrimePi[b];Array[yu,ppi];For[i=1,i≤ppi,yu[i]=Prime[i];i++;];
L5 For[i=2,i≤PrimePi[b/2],For[j=i+1,j≤ppi,s=yu[i]+yu[j];
L6 If[s < b,a[s+1,2]++,Goto[lbl];];j++;];Label[lbl];i++;If[FractionalPart[i/10000]==0,fff=Date[];
L7 Print["Goldbach ",i," sur ",PrimePi[b/2]," en ",FromDate[fff]-FromDate[aaa]," secondes
L8 !"];];];
L9 Array[a,{b,2}]>>valitttopgold;ColumnForm[Array[a,{b,2}]]>>valitttopgoldcolumn;
L10 For[j=1,j≤2*b,If[DivisorSigma[0,j]==4&&Length[FactorInteger[j]]>1&&OddQ[j],Goto[etap];];
L11 c=DivisorSigma[1,j]-j;If[c<=b && c>0,a[c,2]=a[c,2]+1;];Label[etap];j++;];
L12 limm=IntegerPart[b^(3/2)/2.5]+1;Print["limm = ",limm];
L13 For[j=2*b+1,j≤limm,If[DivisorSigma[0,j]==4&&Length[FactorInteger[j]]>1&&OddQ[j],Goto[eetapee];
L14 ];
L15 c=DivisorSigma[1,j]-j;If[c<=b && c>0,a[c,2]=a[c,2]+1;];Label[eetapee];
L16 If[FractionalPart[(j-1)/10^(IntegerPart[Log[10,limm]]-1)]==0,bbb=Date[];
L17 Print["Sigma ",j-1," sur ",limm," en ",FromDate[bbb]-FromDate[aaa]," secondes
L18 !"];];j++;j++;];
L19 d=IntegerPart[Sqrt[limm]+1];If[EvenQ[d],d++;];While[d < b,If[PrimeQ[d],a[d+1,2]++;];d++;d++;];
L20 alimma=IntegerPart[limm^(1/3)]+1;
L21 For[d=alimma,1+d+d^2≤b,If[PrimeQ[d],a[1+d+d^2,2]++;];d++;];
L22 ccc=Date[];Print["Temps total en secondes : ",FromDate[ccc]-FromDate[aaa]];
L23 Print["Temps en secondes pour sigma : ",FromDate[ccc]-FromDate[fff]];
L24 Array[a,{b,2}]>>valitttop;ColumnForm[Array[a,{b,2}]]>>valitttopcolumn;Print["FIN"];)
Commentaire du programme :
Ligne 1 : on entre L qui ici s’appelle b et qui vaut 5 000 000.
Ligne 3 : on initialise un tableau avec b places.
Lignes 4 à 9 : on cherche les nombres de Goldbach (les G(n)). On les stocke dans le fichier « valitttopgoldcolumn). Cette partie traite tous les antécédents de la forme N=pq.
Lignes 10 à 11 : on teste les antécédents pairs et on prend soin de ne pas compter les nombres à 4 diviseurs (N=pq ont 4 diviseurs : 1, p, q et pq) déjà comptés précédemment dans les G(n).
Lignes 12 à la fin : partie classique où l’on teste les antécédents impairs. On traite à part à la fin, les N qui sont des carrés ou des cubes de nombres premiers.
Là aussi, on prend soin de ne plus traiter les nombres à 4 diviseurs.
Notons que pour n impair, A(n) étant donc très fortement dépendant de G(n-1), A(n) dépend au final de la décomposition de n en facteurs premiers. Pour savoir pourquoi, cliquer ici :
Proposition d’une méthode très précise de détermination de l'ordre de grandeur de G(n) (les nombres de Goldbach) pour un n donné en fonction de la décomposition de n en facteurs premiers.
Dernière modification : 29 décembre 2015