Nombres et arborescences

 

Jean SOUSSELIER (04/99)

 

 

Ce mémoire expose une manière de représenter les entiers naturels au moyen des nombres premiers et de leur rang, puis au moyen d’arborescences (chaque entier correspond à une  arborescence et réciproquement), et en déduit diverses conséquences.

 

1 – Nombres

1-1. Définitions

Considérons la table associant les nombres premiers p et leur rang n.

 

p

n

 

2

3

5

7

11

13

17

19

23

29

...

1

2

3

4

5

6

7

8

9

10

...

 

 

Soit P1 l’ensemble des nombres premiers, N l’ensemble des entiers naturels.

Considérons la fonction p  =  P(n) et inversement, le rang n  =  R(p), ces 2 fonctions étant induites par la table ci-dessus.

 

Considérons P2  =  ensemble des nombres premiers dont le rang est premier, c’est à dire :

p2Î P2 Û p2  =  íp, R(p) Î P1ý

 

et plus généralement :

 

pi Î Pi Û pi  =  íp, R(p) Î Pi-1ý

 

Remarquons qu’on a aussi :

 

p2 Î P2 Û p2  =  íp, p =  P(P(n))ý

ou encore p2  =  íp, p =  P2(n)ý

 

et plus généralement :

 

pi Î Pi Û

pi  =  íp, p = Pi(n)ý

 

On a ainsi par exemple :

 

P2 = í3, 5, 11, 17, 31, 41, 59, 67, 83, 109,...ý

P5 = í31, 127, 709, 1787, 5381, 8527, 15299, 19577, 27457, 42043,...ý


Appelons nombres hyper- premiers hi le premier représentant de chaque ensemble Pi  soit

hi Î H Û   hi  =  Pi(1)

H = í2, 3, 5, 11, 31, 127, 709, 5381, 52711, 648391, 9737333,...ý

 

Remarques : 1. C’est une suite de nombre premiers tels que chacun d’eux représente le nombre de nombre premiers inférieurs ou égaux au nombre qui suit. Par exemple, il y a 11 nombres premiers inférieurs ou égaux à 31, 31 inférieurs ou égaux à 127, etc.

Cela est facile à vérifier en considérant la suite des arborescences : le nombre de nombres premiers entre Pj-1(1) et Pj(1) est égal à l’intervalle   [Pj-2(1)+1,Pj-1(1)], c’est à dire à                  Pj-1(1) -Pj-2(1) .

De proche en proche, on établit ainsi la proposition énoncée.

En fait, cette suite de nombres est déjà connue sous le nom de « suite de Wilson ».

 

2. Si on considère les 1 000 000 premiers nombres premiers, ils contiennent :

 

78 498 nombres ÎP2,  7 702 nombres ÎP3,   977 nombres ÎP4,  165 nombres ÎP5,

38 nombres ÎP6, 12 nombres ÎP7,  5 nombres ÎP8,   3 nombres ÎP9

 

 

1-2. Application : nouvelle représentation des entiers.

 

Tout entier naturel peut s’écrire en n’utilisant que la fonction P, l’argument 1, et l’opération produit.

Plus formellement, tout entier s’écrit sous la forme d’une P- expression.

 

Définition d’une P- expression

 

- 1 est une P- expression

- Si e est une P- expression, P(e) est une P- expression

- Si e1 et e2 sont des P- expressions, e1 . e2  est une P- expression

 

Démonstration

 

Il suffit de le démontrer pour les nombres premiers.

 

En effet :

- tout nombre hyper-premier s’écrit :

   Pi(1)  =  P(P(P...(1))...)

- tout nombre premier s’écrit

   p = P(n) et en décomposant n en facteurs premiers :

   p = P(m1 . m2 . m3...)

 

Mais on peut recommencer l’opération avec chaque mi  soit

 

p =  P(P(r1) . P(r2) . P(r3)...)

p =  P(P(s1 . s2...) P(t1 . t2...) ...)

 

jusqu’à ce qu’on ne trouve plus que des nombres hyper-premiers.


On a ainsi :

 

2 = P(1)

3 = P(P(1)) =  P2(1)

4 = P(1) . P(1)

5 = P(P(P(1)) = P3(1)

6 = P(1) . P2(1)

7 = P(P(1) . P(1))

8 = P(1) . P(1) . P(1)

9 = P2(1) . P2(1)

10 = P(1) . P3(1)

11 = P4(1)

12 = P2(1) . P(1) . P(1)

13 = P(P(1) . P2(1))

etc.

 

2- Arbres et arborescences

2-1. Rappels

 

Un arbre est un graphe connexe sans cycle.

Un arbre de n sommets possède (n-1) arêtes.

Dans la figure 1, a, b, e, f, g sont des sommets pendants, c et d sont des sommets connectants.

                                  

                                  

 

                                                                            Fig. 1

 

Une arborescence de racine a est un graphe orienté tel que :

- tout sommet ¹ a est l’extrémité terminale d’un seul arc

- a n’est l’extrémité terminale d’aucun arc


- il n’y a pas de circuit

                                                                            Fig. 2

a3, a4, a5 sont des sommets pendants (ou feuilles).


Remarques :

 

-   Par la suite, nous ne considérerons que des graphes abstraits, c’est-à-dire que les sommets                   

    ne seront pas étiquetés.

-   Toute arborescence est un arbre (en faisant abstraction des orientations des arêtes).

-   Inversement, à tout arbre avec n sommets on peut faire correspondre autant d’arborescences qu’il y a de sommets : il suffit de considérer un sommet comme la racine d’une arborescence, d’orienter les arêtes partant de ce sommet, et de continuer de proche en proche à partir des sommets devenus extrémités terminales de ces arêtes.

     L’absence de circuit de l’arborescence garantit la cohérence de la démarche.

     Ex : avec l’arbre précédent, l’arborescence construite à partir de c donne :


                                                           Fig. 3

 

Par la suite, pour des raisons de commodité d’écriture, nous ne ferons pas apparaître l’orientation des arcs ; par convention, les arcs seront systématiquement orientés du haut vers le bas.

 

2-2. Définitions

 

Nous dirons que 2 arbres sont identiques s’ils sont superposables, c’est à dire si l’on peut faire correspondre leurs sommets de manière biunivoque, 2 sommets liés dans un graphe étant également liés dans l’autre.

De la même manière, 2 arborescences seront identiques si elles satisfont aux mêmes règles, avec de plus la même orientation des arcs.

 

Filiation

 

Dans une arborescence, pour toute arête (a, b) reliant les sommets a et b (de a vers b), a sera appelé le père et b le fils.

La racine n’a pas de père, les sommets pendants (ou feuilles) n’ont pas de fils.

On appellera lignée d’un sommet l’ensemble de ses ancêtres, jusqu’à la racine.

 

Niveau. Par définition, la racine sera le seul sommet de niveau 0.

Ses fils seront de niveau 1.

Plus généralement, les fils des sommets de niveau i seront de niveau i + 1.

 

Branche : on appellera branche issue d’un sommet connectant, la sous- arborescence ayant ce sommet pour racine, l’un quelconque de ses fils, et tous les descendants de ce fils.

Par exemple, dans la figure 2, il y a 2 branches issues de a; à savoir

(a1, a2, a3, a4) et (a1, a5).


2-3. Correspondances entiers- arborescences

 

Les entiers naturels peuvent être représentés d’une manière biunivoque par des arborescences en appliquant les règles ci-dessous:

 

-   Le nombre 1 sera représenté par un simple sommet (arborescence dégénérée sans arête).

-   On va ensuite utiliser la représentation des nombres à l’aide des P- expressions comme décrit au paragraphe 1.2.

-   Si une arborescence de racine a représente le nombre n,     P(n) sera représentée par une arborescence obtenue en rajoutant un sommet b père de a, b étant donc la nouvelle racine.

     (dans la figure 4, l’ovale représente une arborescence de racine a).

 


                                                                            Fig. 4

 

-   Si n et m sont représentés par 2 arborescences de racines a et b, on fera correspondre au produit n.m une arborescence obtenue en réunissant les 2 arborescences par leurs sommets confondus en un seul :

 


                                                                            Fig. 5

 

Avec cette construction, à tout entier correspond une arborescence et une seule, puisque la décomposition de tout nombre en facteurs premiers est unique, et à toute arborescence correspond un entier et un seul.

 

En effet, pour une arborescence de sommet a, il suffit de démontrer la proposition pour une branche issue de ce sommet. Or, la valeur de cette branche est P(n), n étant le nombre correspondant à la sous- arborescence ayant pour racine le fils choisi de a.

On est donc ramené à démontrer l’unicité de valeur de cette sous- arborescence. On continue de proche en proche jusqu’à ce qu’on arrive à une branche composée d’une seule lignée, c’est à dire correspondant à un nombre hyper-premier unique.


2-4. Exemples

 

 

Les nombres de 1 à 20 sont représentés ci-dessous : 

 


           

Fig. 6

 

 

Les nombres premiers sont :


                       

Les nombres hyper-premiers :


                                  

 

 

2-5. Conséquences

 

2-5.1 On déduit immédiatement de ce qui précède que :

 

-   l’on a une méthode pour construire l’ensemble des arborescences, en étant garanti que l’on n’en construira pas 2 identiques.

-   l’on peut énumérer les arborescences.

-   l’ensemble des arborescences est dénombrable, puisqu’il est en correspondance biunivoque avec l’ensemble des entiers naturels.

 

2-5.2 Une autre conséquence est la suivante :

 

L’ensemble des sous-ensembles finis de l’ensemble des entiers naturels est dénombrable.

En effet, considérons un tel sous-ensemble : (n1,n2,…ni,…).

On peut lui faire correspondre d’une manière biunivoque le nombre entier p1.p2….pi..

avec  pi= P(ni)

c.q.f.d.

 

 

 

 

2-6 Correspondance entiers- arbres

 

On a vu qu’à une arborescence, correspondait un arbre et un seul, et inversement qu’à partir d’un arbre de n sommets, on pourrait construire un nombre d’arborescences en nombre au plus égal à n.

Cela entraîne que les arbres constituent une partition des arborescences : un arbre définit une classe d’équivalence de toutes les arborescences qui en découlent, et donc des entiers correspondants.

On a donc les classes d’équivalence suivantes :

(3, 4), (5, 6), (7, 8), (9, 10, 11), (12, 13, 14, 17) etc.

 

 

 

3. Classes.

3.1            Définitions.

Appelons « Classe » C(j) l’ensemble des entiers dont l’arborescence associée est composée de j arcs.

Par exemple :

-         C(0)= í1ý

-    C(1)= í2 ý

-    C(2)= í3,4ý

-    C(3)= í5,6,7,8ý

-         C(4)= í9,10,11,12,13,14 ,16,17,19ý

-         Etc.

Les classes constituent une partition des entiers naturels.

Appelons A(j) le plus grand nombre de C(j), B(j) le plus petit nombre, et M(j) le cardinal de cette classe.

Le nombre de nombres premiers d’une classe C(j) est bien entendu égal à M(j-1).


En effet, tout nombre premier s’écrit p=P(n), et à tout nÎC(j-1) correspond un pÎC(j) et inversement.

Remarques : 1. Si n= p .q, les classes des nombres n, p, q étant respectivement j, k, i, on a :

                             j= k+i . Cela est évident en se rapportant aux arborescences associées.

 

                     2. Chaque classe C(j) contient 2 nombres particuliers : une puissance de 2 : (2j), et un nombre hyper- premier : Pj(1), avec respectivement un seul niveau et une seule lignée.

Par exemple pour la classe 4 : 16 et 11, pour la classe 5 : 32 et 31, pour la classe 6 : 64 et 127.

 

3.2 Conjecture préalable.

Si n>1, on a                             P2(n)         P(n) 

                                               -------   >  ------                        (1)

                                               P(n)            n                 

 

(1)   est vérifiée aisément pour tout n de 2 à 100 000.

On peut penser que (1) est toujours vraie, si on considère que pour n grand, on a :

P(n)~n Log(n).

En effet (1) devient :                 n Log(n) Log(n Log(n))               n Log(n)

                                                ---------------------------     >      ------------       

                                                   n Log(n)                                        n

 

ou encore                                Log(n Log(n))   >   Log(n)

soit                                          Log(n) >1

Pour que cette démonstration soit rigoureuse, il faudrait remplacer l’approximation

P(n)=n Log n par une fourchette de valeurs, peut-être en utilisant l’inégalité de Tchébychev relative à la fonction  Pi(x).

Par la suite, nous supposerons que (1) est vraie.

Remarque : de (1), on déduit que , si i>j, on a :

 

Pi(n)              Pj(n)

------     >     -------

            Pi-1(n)           Pj-1(n)

3.3 Théorème.  Pour toute classe C(j) avec j> 3, on a :

                                  

                                    A(j)= Pj-3(8)                            (2)

 

Il est facile de voir que :

A(1)=2

A(2)=4

A(3)=8

A(4)=19=P(8)

A(5)=67=P(19)=P2(8)

 

Pour démontrer (2), considérons la première valeur de j pour laquelle (2) n’est pas vérifiée, et démontrons que l’on arrive à une contradiction.

 

3.3.1  Tout d’abord, A(j) ne peut pas être premier, sinon on aurait A(j)= P(k), avec kÎC(j-1), et donc k<= Pj-4(8) et donc A(j)= Pj-3(8) . Donc, A(j) n’est pas premier ( ou alors (2) est vérifiée ! ).Donc :

 

A(j)=k1.k2.k3

 

Soient i1, i2, i3 les classes de k1, k2, k3.

On a j=i1+i2+i3+…

Chaque nombre k doit être le plus grand de sa classe, donc :

 

A(j)=A(i1).A(i2).A(i3)…

 

3.3.2   Dans le 2è membre, il ne peut y avoir que 2 termes, sinon on pourrait remplacer par exemple

                        A(i2).A(i3) par le nombre premier A(i2+i3) en vertu de la supposition que j est le premier nombre pour lequel (2) n’est pas vraie.

 

On a finalement :

                        A(j)=A(i).A(k) , soit :   A(j)=Pi-3(8).Pk-3(8)

 

3.3.3   Démontrons d’abord qu’on ne peut avoir k>3. En effet, sinon le nombre Pi-2(8).Pk-4(8)

           qui est de la même classe j est plus grand que le précédent, car

 

                                   Pi-2(8)            Pk-3(8)

                                   --------    >    ----------  

                        Pi-3(8)            Pk-4(8)

(cela résulte immédiatement de la conjecture préalable si i>k).

 

3.3.4   Finalement, on a :        A(j)= A(i).a     avec a=2,4 ou 8 et i>3.

 

On ne peut avoir a=4 ou 8, en vertu de 3.3.2

Il reste donc                 A(j)=A(j-1).2

 

Soit                             Pj-3(8)= Pj-4(8).2

Or, en vertu de la conjecture préalable, on a :

 

 

                                   Pj-3(8)        P(8)

                                   -------   >   -------   > 2

                                    Pj-4(8)           8                                    (car P(8)=19))

 

Cqfd

 

3.3.5  Remarque : Inversement, tout nombre Pj-3(8) est le plus grand de sa classe. Cela est évident si on considère qu’à un tel nombre correspond une classe et une seule et inversement.

 

 

3.4  Théorème.  Pour toute classe C(j), avec j>3, on a :

 

                                   B(j)= 3a . 5b                (3)

 

            Avec :              2a+3b=j          et         0<=a<=2

 

On a :  B(1)=2

            B(2)=3

            B(3)=5

            B(4)=9

            B(5)=15

 

3.4.1  Démontrons d’abord que B(j) n’est pas premier si j>3. Pour j=4 ou 5, cela est vrai.

            Au-delà, s’il l’était, on aurait    B(j)=P(n)         n étant de classe (j-1).

 

Il suffit de démontrer que   P(n)>2.n    à partir de n=5 (puisque P(n) et 2.n sont de la même classe j). On a évidemment

                        P(n+1)-P(n)>=2

 (l’intervalle entre 2 nombres premiers est au moins égal à 2), et donc de proche en proche :               P(n)-P(5)>=2.(n-5)

Soit                  P(n)>=2.n+1    (puisque P(5)=11).

 

3.4.2   On a donc      B(j)= k1.k2.k3

 

 Soient i1, i2, i3 les classes de k1, k2, k3.

On a j=i1+i2+i3+…

 

           

Chaque nombre k doit être le plus petit de sa classe, donc :

 

B(j)=B(i1).B(i2).B(i3)…

 

Mais comme B(i) ne peut être premier si i>3, cela signifie que B(j) est le produit de nombres uniquement de classes 1,2 ou 3, c’est-à-dire les nombres 2,3 ou 5.

 

3.4.3    Si j>3, B(j) ne peut pas être un multiple de 2 . C’est vrai pour j=4 ou 5. Au-delà :

 

-         B(j) ne peut pas être multiple de 2 uniquement : car on pourrait remplacer 4 par 3, 8 par 5 etc. en restant dans la même classe et en faisant ainsi décroître B(j).

-         Si B(j) est multiple de 2 et de 3, on pourrait remplacer 6 par 5 qui est de la même classe (3) et qui fait ainsi décroître B(j).

-         Pour les mêmes raisons, si B(j) est multiple de 2 et de 5, on peut remplacer 10 par 9 (classe 4).

3.4.4    B(j) est donc multiple de 3 et de 5 uniquement. La puissance maximum de 3 ne peut être que 2. En effet, si B(j) était multiple de 27, on pourrait remplacer 27 par 25 en restant  dans la même classe (6) et en faisant ainsi décroître B(j).

Finalement, B(j) est de la forme           5b,3.5b,9.5b

cqfd

 

                             

3.4.5  Remarque : Inversement, pour tout couple a et b avec             0<=a<=2        

le nombre         3a . 5b                                   est le plus petit de la classe j=2a+3b.

Cela est évident car à tout tel couple a et b correspond une classe j et une seule et inversement, à toute classe j, correspond un couple et un seul satisfaisant aux conditions précédentes.     

 

 

 

3.5       Algorithme.

 

Ci-après est donné un algorithme pour calculer de proche en proche le nombre M(j) de nombres d’une classe C(j), c’est-à-dire le nombre d’arborescences ayant j arcs.

 

3.5.1    Les nombres de la classe C(j) peuvent se répartir en 3 sous-classes C1,C2 et C3 de cardinaux respectifs M1(j),M2(j) et M3(j), à savoir :

 

-         C1(j) : ensemble des nombres premiers de C(j)

-         C2(j) : ensemble des nombres pairs de C(j)

-         C3(j) : ensemble des nombres impairs non premiers de C(j).

-          

On a :                          M(j)=M1(j)+M2(j)+M3(j)      (pour j>1).

 

et                                 M1(j)=M(j-1)

                                   M2(j)=M(j-1)

 

(pour des raisons évidentes de construction : tout nombre pair s’écrit    2.n,   n étant de classe  (j-1), et tout nombre premier étant P(m), m étant de classe (j-1)).

 

Il reste à déterminer M3, ce que nous allons faire de proche en proche, en connaissant les valeurs de M1, M2 et M3 pour les premières valeurs de j.

 

3.5.2.  Tout nombre  aÎC3(j) s’écrit :           a=a1.a2 .a3….,chaque facteur étant un nombre premier de classe i1,i2 ,i3….avec :             j= i1 +i2 +i3…. et   ik>=2 , et réciproquement, on peut construire l’intégralité de C3(j) en considérant :

 

-         toutes les suites ik d’au moins 2 termes satisfaisant aux conditions :

 

            j= i1 +i2  +i3…. et   ik>=2,

 

- pour chacune de ces suites, on considère tous les produits     a=a1.a2 .a3…, chaque ak  étant un nombre premier de classe ik, c’est-à-dire              akÎC1(ik)

 

Ces suites définissent une partition de C3 ; pour connaître M3, il suffit de calculer le nombre de produits « a » pour chaque suite , et de sommer sur l’ensemble des suites.

 

Pour une suite donnée, supposons d’abord que tous les ik  sont différents. Alors tous les ak sont  différents, et le nombre de produits cherché est :

 

                                               M1(i1) .M1(i2).M1(i3)…

 

S’il y a 2 ik identiques, il faut remplacer            M1(ik) .M1(ik)   par     M1(ik) .(M1(ik )+1)/2

 

 Nous en verrons plus loin la généralisation.

 

 

3.5.3 Exemple.  Connaissant les valeurs de M1,M2 et M3 pour j=2,3 et 4, calculons les pour j=5 à 7.

 

                                   j           M1      M2      M3      M

                                   --------------------------------------

                                   2          1          1          0          2

                                   3          2          2          0          4

                                   4          4          4          1          9

 

Pour j=5, on a             M1=M2=9

                                    La seule suite à considérer pour calculer M3 est

                                   (3,2) conduisant à M3=2 , d’où M=20.

 

Pour j=6, on a             M1=M2=20

                                    Les suites à considérer pour calculer M3 sont :

                                   (4,2) donnant la valeur 4,

                                   (3,3) donnant la valeur 3,

                                    (2,2,2) donnant la valeur 1, soit au total M3=8 et M=48.

 

Pour j=7, on a             M1=M2=48

                                    Les suites à considérer pour calculer M3 sont :

                                   (5,2) donnant la valeur 9,

                                   (4,3) donnant la valeur 8,

                                    (3,2,2) donnant la valeur 2, soit au total M3=19 et M=115.

 

En continuant la méthode, on obtient les résultats suivants :

 

                                   M(8)=286

                                   M(9)=719

                                   M(10)=1842

 

 

3.5.4    Précisions sur la méthode. L’algorithme décrit est particulièrement simple, mis à part les deux points suivants : l’énumération de toutes les suites (i1 ,i2  ,i3…)  et le calcul  du nombre de produits différents lorsque plusieurs ik  sont identiques .

 

3.5.4.1  Enumération des suites (i1 ,i2  ,i3…), vérifiant les conditions :

                       

                                                i1 +i2 +i3…=j    et   ik>=2

Cette énumération est très simple si on prend soin d’écrire chaque suite de telle manière que :

 

                                   i1 >=i2 >=i3>=…>=2

 

Il suffit de partir de la première suite :(j-2,2) , puis de passer d’une suite à la suivante en appliquant les règles suivantes : on cherche, en partant de la droite, le premier ik qui n’est pas un 2 . On remplace ik par ik –1, et on prolonge la suite en prenant la plus grande valeur compatible avec les conditions ci-dessus, et ainsi de suite ; en cas d’échec, on revient en arrière et ainsi de suite.

 

3.5.4.2 Calcul de la valeur devant remplacer M1(ik) .M1(ik) .M1(ik)…, lorsqu’une suite contient plusieurs valeurs ik identiques.

Traitons le problème généralement en changeant les notations : on dispose d’une collection de n nombres (a1 ,a2  ,a3…) tous différents.

On cherche le nombre de couples, triplets, etc. (m-plets) différents, soit N(n,m).

Cette détermination est très simple si on prend soin d’écrire un tel m-plet sous la forme :

 

ai.aj.ak…, avec i<=j<=k<=…

 

On a évidemment :

                        N(n,1)=n

                       

                        N(n,2)=n+(n-1)+(n-2)+……+1

 

                        N(n,3)=N(n,2)+N(n-1,2)+N(n-2,2)+……+N(1,2)

                        ------------------------------------------------------------

                        N(n,m)=N(n,m-1)+N(n-1,m-1)+……..+N(1,m-1)

 

 

Donc, connaissant   n= M1(ik), et le nombre m de répétitions de ik , on peut aisément calculer le nombre cherché.

 

 

 

3.6  Théorème.  Si n Î C(j)  et n>2.A(j-1),  è    n Î C1(j)

 

Dans une classe j, les nombres supérieurs à 2.A(j-1) sont premiers.

 

Démonstration : n ne peut pas être pair, sinon il vaudrait 2.m, m étant de classe (j-1), et donc inférieur à A(j-1).

 

Donc n est impair,        n=a1.a2 ,           a1 et a2   étant 2 facteurs quelconques de classe i1 et i2 , avec     i1 + i2 =j

 

Il suffit de démontrer que         A(i1 ).A(i2 )<=2.A(j-1)

 

Or cela découle de la conjecture préalable, comme dans 3.3.3, on a en effet :

 

                        A(i1 ).A(i2 )<= A(i1+1).A(i2-1) si  i1>i2 , et ainsi de suite.

Cqfd

 

Exemples :

 

dans la classe 5, tous les nombres supérieurs à 2.A(4)=38 sont premiers :(41,43,53,59,67).

dans la classe 6, tous les nombres supérieurs à 2.A(5)=134 sont premiers :(139,157,163,179,191,193,…).

 

Conséquence : Dans une classe C(j) , on a :

 

-  plus petit nombre premier :   P(B(j-1))         (évident)

-  plus grand nombre premier :             A(j)=P(A(j-1))           

-  plus petit nombre non premier :         B(j)

-  plus gand nombre non premier :        2*A(j-1)          (découle de ce qui précède).