NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 23/04/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

COMPTER - Combinatoire

 

Débutants

Dénombrement

FACTORIELLES

 

Glossaire

Combinatoire

 

 

INDEX

 

Compter

 

Dénombrer

 

 

Index factorielle

Introduction

Super-factorielles

Primorielle

Super-primorielle

Comporielle

 

Sommaire de cette page

>>> Primorielle

>>> Valeurs

>>> Primorielles et premiers

>>> Primorielle et recherche des nombres premiers par PGCD

>>> Premiers dans l'intervalle

>>> Primorielle premières

>>> Plage de composés derrière la primorielle

>>> Super-primorielles

>>> Table

>>>  Algorithme de recherche des premiers par modulo

 

 

 

 

PRIMORIELLES

&

Super-primorielles

 

Les primorielles sont construites comme les factorielles, mais en ne retenant que les nombres premiers successifs.

Elle est notée n#. 

Par exemple   5#  = 1 x 2 x 3 x 5 = 30 (sans le 4)

Nom donné par Harvey Dubner.

Les super-primorielles sont une extension des primorielles avec facteurs premiers portés à une puissance particulière.

Anglais - Primorial

 

 

PRIMORIELLE (n)

 

Définition

 

Produit des nombres premiers successifs jusqu'à n, n compris s'il est premier. Noté n# ou, parfois P(n).

Exemples

P(5) = 5# = 1 x 2 x 3 x 5 = 30

P(6) = 6# = 1 x 2 x 3 x 5 = 30

P(7) = 7# = 1 x 2 x 3 x 5 x 7= 210

P(8) = 8# = 1 x 2 x 3 x 5 x 7= 210

 

Valeurs successives

 

2#  = P   (2)

= 2

= 2

=   1 x 2

3#  = P   (3)

= 2 x 3

= 6

=   2 x 3

5#  = P   (5)

= 2 x 3 x 5

= 30

=   5 x 6

7#  = P   (7)

= 2 x 3 x 5 x 7

= 210

= 14 x 15

11#  = P (11)

= 2 x 3 x 5 x 7 x 11

= 2 310

= 42 x 55

13#  = P (13)

= 2 x 3 x 5 x 7 x 11 x 13

= 30 030

= 165 x 182

17#  = P (17)

= 2 x 3 x 5 x 7 x 11 x 13 x 17

= 510 510

= 714 x 715

 

 

Propriétés

 

*       Du fait de leur définition (se référer à la table ci-dessus):

*    Un nombre hautement composé ne contient aucun facteur carré.

*    La quantité de facteurs croît également en passant d'un nombre hautement composé au suivant.

 

*       Les primorielles de 2, 3, 5, 7 et 17 peuvent être représentées comme produit de deux nombres consécutifs. Ce sont les seules valeurs ayant cette propriété.

 

*       Les valeurs des primorielles croissent rapidement. Il est vrai que la plupart des entiers ont très peu de diviseurs premiers distincts. Les primorielles, bien qu'en nombre infini, sont exceptionnelles, très peu dense parmi les entiers.

 

*       Tout nombre hautement composé est un produit de primorielles.

 

Moyenne selon les plages

   

10²

=>

1,71

108

=>

2,9

10100 = 1 googol

=>

5,4

10googol

=>

23,9

 

 

Primorielles – Table

Voir TableIndex

 

 

 

 

Primorielles et infinité de premiers

*       Soit n le plus grand nombre premier.

n le plus grand des premiers

*       Et, étudions le nombre N.

Deux cas possibles =>

N = n# + 1

N premier ou pas

Cas 1) – Supposons N premier.

*       Pas possible car N serait un premier plus grand que n; ce qui est contraire à notre hypothèse.

alerte1.jpg Contradiction

 

N > n

N serait un premier encore plus grand que n

Cas 2) – Supposons N composé.

*       N a au moins un diviseur premier d.

*       Il est plus petit que n, le plus grand des premiers.

*       Or n!! est le produit de tous les premiers jusqu'à n; le diviseur d est parmi eux.

*       Si d divise à la fois N et n#

il divise n# et n!! +1

Il divise 1.

Rappel: la barre verticale veut dire "divise".

*       Or, d est un diviseur premier, donc différent de 1.

alerte1.jpg Contradiction

 

N  = … x d x

               d < n

 

n# = … x d x

 

d  n# + 1 = N

d  n#

d  1

 

d  1

*       Les deux cas analysés conduisent à une contradiction qui atteste que l'hypothèse est fausse. Il n'y a pas un nombre premier le plus grand. Ils sont en nombre infini.

n le plus grand des premiers: FAUX

Infinité de premiers.

Voir Infinité de nombres premiers

 

 

Primorielle et recherche des nombres premiers

Exploitation de la propriété concernant le PGCD d'une primorielle (2x3x5 …p) avec un nombre (n) plus grand que p.

 

Alors, le plus petit nombre n avec PGCD  = 1 est un nombre premier.

Exemple: n = 10 => Prim (<10) = 2x3x5 = 30

PGCD(10, 30) = 10 => 10 est composé

PGCD(11, 30) = 1 => 11 est premier.

 

 

Pour accélérer la recherche, seuls les nombres en 6k  1 sont examinés.

En effet, tous les nombres premiers sont de la forme p = 6k  1.

Programme

 

Commentaires

On commence en traitant séparément le cas des nombres 2 et 3 mis dans une liste (L) et on compose la première primorielle Prim.

 

Boucle qui commence à 6 et qui progresse de 6 en 6 (by 6).

 

Traitement du cas 6k – 1. Si  le PGCD (gcd en anglais) est égal à 1, on complète la liste L.

Traitement du cas 6k + 1. Si  le PGCD (gcd en anglais) est égal à 1, on complète la liste L.

 

Après avoir indiqué la fin de la boucle (od, le do à l'envers), impression de la liste.

 

 

 

En bleu, la liste calculée en un temps nettement plus rapide que l'application du crible d'Ératosthène.

 

 

 

Note: programme peu malin car le calcul du PGCD, inclus dans le logiciel Maple, est lui-même basé sur la connaissance des nombres premiers.

 

ALORS?

Comment se passer du PGCD? Utiliser les super-primorielles!

 

 

 

 

 

 

Premiers dans l'intervalle

 

Petit dessin pour situer les nombres premiers tels que montrés dans la démonstration:

Ce dessin illustre le fait qu'il existe toujours un nombre premier entre n et N = n# + 1 (primorielle).

Avec une démonstration du même type, on peut montrer qu'il existe toujours un nombre premier entre n et N = n! + 1 (factorielle).

L'intervalle avec la primorielle (nombres premiers) est plus petit que celui avec factorielle (tous les nombres).

Voir Propriétés des nombres premiers

 

 

 

Primorielle première

 

Comme pour les factorielles, on se pose la question de savoir si les primorielles plus un ou moins un sont des nombres premiers.

 

Liste des primorielles premières jusqu'à 3000



 

Plage de nombres composés derrière la primorielle

 

Comme pour les factorielles, les primorielles sont suivies d'une quantité minimale de nombres composés.

 

En omettant le suivant (+1) qui peut être premier, les p suivants sont composés.

*        n# + 1 peut être premier;

*        n# + p est le dernier composé naturel;

*        n# + p+1, avec p + 1 nécessairement pair, est un composé; et

*        les suivants sont indéterminés.

 

 

Exemple avec primorielle 7 = 210

 

 

Note: 222 = 2 x 3 x 37 ; 223 est premier;
          soit d = 11 composés derrière 211.

 

 

Plage de nombres composés derrière une primorielle

 

Ce tableau donne la quantité d de nombres composés qui suivent le nombre n# + 1. Il est toujours égal ou plus grand que n (sauf pour 2). L'excédent d – n tend à croître avec n, mais souffre d'exceptions, comme avec 59#.

 

 

Merci à Louis F. pour ses judicieuses remarques

 

Une certaine manière de voir la notion de Plus Petit Commun Multiple des nombres de 1 à N

 

Super-primorielles ou PPCM (1..N)

 

Définition

La super-primorielle d'un nombre N est une primorielle dont les facteurs premiers sont portés à une certaine puissance en rapport avec N.

En fait, parmi les facteurs de la super-primorielle de N, on compte toutes les puissances des facteurs premiers inférieures à N.

 

 

SP(N) = 2a . 3b . 5c . 7d . …

Avec 2a < N et 2a+1 >N

          3b < N et 2b+1 >N

          Etc.

 

Exemple

SP(10) = 23 . 32 . 5 . 7 = 2 520

Car on trouve (2, 22, 23) et  (3 et 32) jusqu'à 10.

 

En fait:

SP(10) = PPCM (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

 

 

Exemple pour N = 10, la super-primorielle vaut 2 520

La super-primorielle contient toutes les puissances des nombres premiers inférieures à un nombre donné N.

 

Calcul

Comment déterminer la puissance maximale de chaque facteur premier.

Un nombre premier (p) à la puissance k doit être inférieur à N.

Le passage aux logarithmes permet le calcul de l'exposant. La puissance à retenir est l'entier obtenu en ignorant la partie décimale.

 

Exemple

 

 

Propriété

La super-primorielle offre un avantage sur la primorielle simple en termes de divisibilité.

 

Autre définition de la super-primorielle de N: nombre divisible par tous les nombres qui sont inférieurs à N, ce qui est la définition du plus petit commun multiple (PPCM) de tous les nombres de 1 à N.

 

Tous les nombres inférieurs à N sont divisibles par la super-primorielle de N.

 

Exemple

SP(10) = 2 520 est divisible par 8, car 23 est l'un des facteurs; de même, il est divisible par 9, car 32 est l'un des facteurs.

 

 

Table des super-primorielles jusqu'à N = 50

Voir TableIndex

 

 

Idée d'un algorithme de recherche des nombres premiers

Yves Roques est l'auteur d'un algorithme de recherche des nombres premiers qui exploite la propriété des super-primorielles.

Pour une étendue de recherche jusqu'à N, l'idée consiste à construire la super-primorielle de N au fur et à mesure de la détection des nombres premiers. La super-primorielle y est nommée: NEA = Nombre Entier Atomique.

Voir cette vidéo >>>

 

Le chapitre ci-dessous reprend les travaux d'Yves Roques et ajoute une variante

 

Application: recherche de nombres premiers

Le programme Maple vu ci-dessus peut être amélioré en s'affranchissant du calcul du PGCD. Il est remplacé par une division, ou plutôt un calcul modulo, testant simplement la divisibilité.

 

 

Ce qu'il faut comprendre: le programme sait reconnaitre les nombres premiers, mais une fois la primorielle calculée, les nombres premiers antérieurs sont enfouis. Ils ne sont plus accessibles. D'où l'idée d'en faire usage complètement dès qu'ils se présentent, et ceci, en calculant la super-primorielle. 

 

Programmation

 

Après réinitialisation, mise à 1 de la super-primorielle et spécification de la limite de calcul (N = 10)

Lancement d'une boucle d'exploration des nombres de 2 à N.

Si la super-primorielle n'est pas divisible par  le nombre en cours d'exploration, alors  il s'agit d'un nouveau nombre premier.
On calcule l'exposant à lui attribuer pour trouver la puissance la plus grand inférieure à N. L'instruction trunc tronque la partie décimale et conserve l'entier.

Cette puissance avec cet exposant est introduite dans la super- primorielle.

Impression de i, la nouvelle puissance. Ici, on a aussi imprimé quelques paramètres supplémentaires pour information.


 

 

Accélération de l'exploration

 

L'idée, comme pour le programme mis au point ci-dessus, consiste à ne balayer les nombres autour des multiples de 6.

 

Pour cela, on traite d'abord le cas particulier des nombres 2 et 3. On calcule la valeur de la super-primorielle (SP) pour ces deux cas et on initialise une liste (L) de nombre premiers en y déposant les nombres 2 et 3.

 

La boucle d'exploration commence par 6 et progresse par pas de 6.

 

 

Cas ou i – 1 (ce qui donne 5 pour le premier passage avec i = 6). Si ce nombre ne divise pas SP alors il s'agit d'un nouveau nombre premier. On calcule son exposant  pour introduction dans la super-primorielle. Et, bien sûr, ce nouveau premier est ajouté à la liste.

 

 

Cas ou i –+1 (ce qui donne 7 pour le premier passage avec i = 6). Même type de traitement que ci-dessus.

 

Fin de boucle (od).

 

 

Édition de la liste et de la quantité d'éléments qu'elle contient.

 

 

 

En bleu, affichage des résultats de traitements. On vérifie que le programme édite bien les 25 nombres premiers qui existent jusqu'à 100.

 

Voir ProgrammationIndex

 

 Bilan sur la recherche des nombres premiers

Un premier programme exploite la primorielle et détecte les nombres premiers  au moyen d'une instruction de calcul de PGCD. Intéressant, mais cette instruction  "connait" les nombres premiers. Intérêt comme exercice de programmation.

Le second programme exploite la super-primorielle et ne fait aucune hypothèse sur la connaissance des facteurs premiers des nombres. Elle calcule le PPCM des nombres successifs. Procédé astucieux mais avec un inconvénient, la super-primorielle devient vite un très grand nombre à manipuler. Néanmoins Maple calcule les 9 592 premiers nombres premiers jusqu'à 100 000 en 12 secondes alors que Sp = 6,95… 1043 451.

 

Grand Merci à Yves Roques pour une belle extension de cette page

 

 

Suite

*       Comporielles

*       Voir haut de page

*       FactorielIndex

Voir

*       DénombrerIndex

*       Factorielles

*       Nombres entiers

*       Primorielle et suite de nombres composés

*       Primorielle première

*       Théorème de Wilson

*       Théorie des nombresIndex

DicoNombre

*       Nombre 210

*       Nombre 510 510

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Compter/Factprim.htm