Nombre d'antécédents aliquotes

Télécharger le nombre d'antécédents aliquotes pour tous les entiers jusqu'à 5 000 000.
Attention : 1 a en réalité une infinité d'antécédents aliquotes : tous les nombres premiers. C'est la seule valeur inexacte du tableau. Si elle est finie, c'est parce que dans l'intervalle étudié, il n'y a qu'un nombre fini de nombres premiers.

Retour à page d'accueil

Préliminaires nécessaires à la détermination de A(n), le nombre d’antécédents aliquotes de n.

• Conjecture de GOLDBACH :

Christian Goldbach est né en 1690 et mort en 1764. Ainsi, cette conjecture est vieille de presque 300 ans et elle est devenue l’une des plus célèbres conjectures des mathématiques. La voici :

Tout nombre pair supérieur ou égal à 8 peut s’écrire comme somme de deux nombres premiers.

En ce qui me concerne dans tout ce qui va suivre, les seuls cas qui m’intéressent moi sont ceux où l’on prend les deux nombres premiers distincts et différents de 2.

• Suites aliquotes monotones arbitrairement longues ou lien entre la conjecture de Goldbach et le nombre d’antécédents aliquotes d’un nombre impair :

Soit un nombre impair n. Soit A(n), le nombre de ses antécédents aliquotes.
Soit le nombre pair n-1 (celui précédant juste n) et G(n-1) le nombre de manières différentes d’écrire n-1 comme somme de deux nombres premiers p et q (pris ici distincts et différents de 2). Alors on a nécessairement :

A(n)≥G(n-1)

En effet, si p + q = n - 1 qui est pair, alors le nombre m = pq est antécédent aliquote du nombre impair n. La somme des diviseurs stricts de m=pq est bien 1 + p + q = n, car p et q sont des nombres premiers distincts.
En général dans la pratique, A(n) est toujours un « peu plus grand » que G(n-1). Je n’ai d’ailleurs pas vérifié s’il y a des nombres pour lesquels ils sont égaux ni quels seraient ces nombres (cela devrait être intéressant) !

La conjecture de Goldbach qui implique l’existence de p et q pour le pair n-1 implique donc l’existence de l’antécédent aliquote m=pq de l’impair n.
Notons cependant que m est en général très supérieur à n.
De plus, m=pq est à son tour impair et l’on peut continuer le processus pour lui-même et ainsi de suite aussi loin que l’on veut. On peut donc remonter une suite aliquote à l’envers aussi loin que l’on veut, les termes étant alors strictement croissants (décroissants si on reprend la suite aliquote à l’endroit).

On peut donc affirmer qu’il existe bien des suites aliquotes qui « viennent de l’infini » !
Cette existence ne sera bien sûr démontrée que quand la conjecture de Goldbach le sera !

À titre d’exemple :

Je me suis amusé à remonter des suites aliquotes à l'envers selon ce principe !

Voir les résultats de ce travail

Programme très performant de détermination des A(n), les nombres d’antécédents aliquotes des nombres n compris entre 1 et L, n quelconque :

Un programme très basique consisterait à tester tous les nombres jusqu’à (L-1)². En effet, si N > (n-1)², alors σ'(N) > n. Le lecteur se convaincra facilement de la chose en réfléchissant 5 minutes. En améliorant un peu la méthode, on pourra se contenter de tester les nombres seulement jusqu’à 0.25L².
Mais, on peut faire bien mieux encore !!!
Il nous faut d'abord différencier les cas où N est pair et impair.
En effet, si N est un antécédent de n et est pair, dès que N > 2n on a σ(N) > 1 + 2 + 2n/2 = 3 + n > n. Il est donc inutile de tester les N pairs supérieurs à 2n pour trouver les antécédents de n !
Voyons désormais le principe du nouveau programme.

Notre problème est de trouver A(n) pour tous les nombres n compris entre 1 et L.

Comme nous venons de le voir, il nous faut tester tous les N pairs compris entre 1 et 2L. Ces L tests de nombres pairs ne sont pas un problème et ne nécessitent pour leur traitement qu’une infime partie du temps de calcul.

Le cas des N impairs est tout différent. Il nous faut faire l’inventaire de ses différentes formes, mais en rappelant juste avant que notre ambition est de ne pas devoir tester les antécédents N impairs au-delà de L^3/2/2.5 :

• 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’à L^3/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 = p³. Ici, si on néglige les termes de plus bas degré, N ~ L^3/2. Ou, dit autrement, ce sont les cubes de nombres premiers qui nous obligent à tester les antécédents jusqu’à N = L^3/2. Certains antécédents de ce type peuvent donc être oubliés dans notre programme où l’on ne teste que jusqu’à L^3/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+p²+…+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’à L^3/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 L^3/2/2.5 = 400 < L^4/3 ≈ 464, ce qui pose problème ! Si L > 244, L^3/2/2.5 > L^4/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 = 2x^3/2/(3^3/2)≈(1/2.598)x^3/2

Concrètement, nous allons majorer et prendre :

N = (1/2.5)×n^3/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.

Programme très performant de détermination des A(n), les nombres d’antécédents aliquotes des nombres n compris entre 1 et L, n uniquement pair :

Soit n un nombre pair dont je veux trouver tous les antécédents aliquotes. Soit N un de ses antécédents aliquotes. Il y a deux cas possibles quant à la parité de N : soit il est pair, soit il est impair.

Si N est pair :
Si N=2i avec i≥n, alors σ’(N)≥1+2+i>n. Il est donc suffisant de tester tous les entiers pairs N≤2n pour avoir tous les antécédents pairs de n.

Si N est impair :
Si N est impair et s’il est antécédent de n qui est pair, alors, il est nécessairement de la forme suivante : N=i² avec i entier et impair (voir le lien changement de parité, les cas N=2i² et N=i² avec i pair ont été examinés précédemment dans la recherche des antécédents pairs). Si N=i² avec i≥n, alors σ’(N)≥1+i>n. Il est donc suffisant de tester tous les nombres impairs N=i² avec i impair tel que 1<i≤n pour avoir tous les antécédents impairs de n.

D’où la méthode :
Pour connaître tous les antécédents d’un nombre pair n (ou de tous les nombres pairs jusqu’à n, ce qui revient au même), il me suffit de tester tous les nombres pairs jusqu’à 2n et tous les carrés parfaits de tous les impairs compris entre 1 et n.

Dernière modification : 29 décembre 2015