|
||||||||||||||||||||||||||||
|
PRIMORIELLES Produit des nombres premiers & 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# = 2 x 3 x 5 = 30
(premiers jusqu'à 5) ou aussi 5# = 2 x 3 x 5 x 7 x 11 = 2 310
(cinq premiers). Nom donné par Harvey
Dubner. Les super-primorielles sont une extension
des primorielles avec facteurs premiers portés à
une puissance particulière. |
Voir Somme
des nombres premiers
Anglais - Primorial
|
|
|||||||||||||||||||||||||||||||||||||||||
|
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
Moyenne
selon les plages
|
|||||||||||||||||||||||||||||||||||||||||
Voir Table – Index
/ Primorielle
29
|
|
|||
|
|
n le plus
grand des premiers |
||
|
Deux cas
possibles => |
N = n# +
1 N premier
ou pas |
||
|
Liste
des nombres d'Euclide E
= n# + 1 |
2, 3, 7, 31, 211, 2311, 30031,
510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304250263527211, … OEIS
A006862 En
rouge, les nombres d'Euclide premiers. |
||
|
Cas 1) – Supposons N premier.
|
N > n N serait
un premier encore plus grand que n |
||
|
Cas 2) – Supposons N composé.
il divise n# et n!! +1 Il divise 1. Rappel: la
barre verticale veut dire "divise".
|
N = … x d x … d < n n# = … x d x … d d d d |
||
|
|
n le plus
grand des premiers: FAUX Infinité
de premiers. |
||
Voir Infinité
de nombres premiers / Nombres
d'Euclide = n# + 1
Nombres fortunés – Nommés d'après Reo Fortune(1903-1979)
|
Nombres Fortuné: F =
Premier – Primorielle Primorielle: produit des n premiers nombres premiers. Premier: celui juste supérieur à la primorielle, écart supérieur à 1. Fortune
conjecture que ces nombres sont toujours premiers. EN 2020, tous les nombres fortuné connus sont effectivement
premiers, mais la conjecture n'est pas démontrée. Premières valeurs: Primorielle, premier, Fortuné 1,
3, 2 2,
5, 3 6,
11, 5 30,
37, 7 210,
223, 13 2310,
2333, 23 30030,
30047, 17 510510,
510529, 19 9699690,
9699713, 23 223092870,
223092907, 37 6469693230,
6469693291, 61 200560490130,
200560490197, 67 7420738134810,
7420738134871, 61 304250263527210,
304250263527281, 71 Liste selon rang: 3,
5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103,
79, 151, 197, 101, 103, 233, 223, 127, 223, 191, 163, 229, 643, 239, 157,
167, 439, 239, 199, 191, 199, 383, 233, 751, 313, 773, 607, 313, 383, 293,
443, 331, 283, 277, 271, 401, 307, 331, ...
OEIS A005235 Liste selon valeur: 3,
5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109,
127, 151, 157, 163, 167, 191, 197, 199, 223, 229, 233, 239, 271, 277, 283,
293, 307, 311, 313, 331, 353, 373, 379, 383, 397, 401, 409, 419, 421, 439,
443, 457, 461, 491, 499, 509, …. OEIS
A046066 |
|
|
|||
|
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. 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 |
En effet, tous
les nombres premiers sont de la forme p = 6k |
||
|
|
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! |
||
Voir Programmation
– Index
|
|
|
|
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). |
|
|
|
|
|
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
Primorielle
première – 1 ou Primorial -1 primes
|
|
|
|
||
|
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.
|
Exemple avec primorielle 7 = 210
Note: 222 = 2 x 3 x 37 ; 223
est premier; |
|
|
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 3b+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. |
La super-primorielle de N est divisible par tous les nombres
inférieurs à 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. |
|
Merci à Didier T.
Table des super-primorielles jusqu'à N
= 50
Voir Table – Index
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. 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 Programmation – Index
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 |
|
|
Voir |
|
|
DicoNombre |
|
|
Cette page |
