Je vous propose de redécouvrir les Nombres Premiers sous l'angle de la Théorie Algorithmique des Nombres. Puisqu'ils sont à la base d'un ensemble aussi « simple » que les nombres entiers, (par combinaisons multiplicatives et même additives, comme le laisse supposer la conjecture de Goldbach), ils ne devraient pas être si compliqués que ça...Nous allons procéder en deux parties : d'abord, nous allons les décortiquer, les analyser pour découvrir leur « structure interne » qui permettra de les reconstruire. Ensuite, nous allons examiner cette structure pour extraire des informations utiles et intéressantes, et peut-être percer quelques vieux mystères...Pour lire la suite, pas besoin d'être « fort en Mathématiques », puisque l'outil central est l'Algorithmique, avec quelques exemples simples en JavaScript.
1. Comment sont construits les Nombres Premiers ?
1.1 Et déjà, qu'est-ce qu'un Nombre Premier ?
Nous allons commencer par rappeler la définition suivante :
- Un nombre premier est un entier naturel strictement supérieur à 1, divisible seulement par 1 et par lui-même [1].
On peut aussi la trouver sous cette forme :
- Un nombre premier est un entier possédant exactement 2 diviseurs (ces deux diviseurs sont donc 1 et lui-même) [2].
Par exemple, 6 peut être décomposé comme 6×1 ou 2×3, ce qui fait 4 diviseurs. C'est donc un nombre dit « composé ». Par contre, le nombre 7 est dit « premier » parce qu'il ne donne pas de résultat entier lorsqu'il est divisé par d'autres nombres que 7 et 1.
Le nombre 1 est mentionné dans la définition, un peu comme une exception. Il est très spécial dans l'ensemble des nombres, puisqu'il est l'élément neutre de la multiplication. Il est aussi indispensable à la définition de tous les autres nombres. Nous en reparlerons dans la deuxième partie...
La définition semble aussi impliquer qu'une division est nécessaire pour trouver si un nombre est Premier. Lorsque ce n'est pas une division, c'est une opération de modulo (le reste de la division entière) qui est utilisée (par exemple pour le test de Miller-Rabin [3][3'] ou Solovay-Strassen [4]). Cela revient au même, puisqu'une division est une succession de soustractions et on s'intéresse soit au reste, soit au nombre de soustractions. Corollairement, peut-on utiliser des additions successives pour construire des nombres premiers ?
1.2 Comment obtenir des Nombres Premiers ?
On sait depuis l'Antiquité construire l'ensemble des Nombres Premiers (noté ici P) avec le crible d'Ératosthène [5]. C'est une méthode rudimentaire mais efficace : on met dans un tableau tous les nombres successifs et on les élimine progressivement. Pour les besoins de cet article, on va éliminer un nombre en le remplaçant par un point. Pour chaque passe, on prend le premier nombre non éliminé du tableau, que l'on considère alors comme premier, puis on élimine tous ses multiples (on les marque comme composés). Cette élimination est itérative, il suffit de balayer le tableau toutes les N cases si N est déterminé comme premier.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . .
etc.
Evidemment, au bout de plusieurs passes, un nombre composé peut avoir été éliminé plusieurs fois (autant de fois qu'il y a de facteurs possibles), mais ce n'est pas important. Seuls les nombres qui restent nous intéressent puisqu'ils sont premiers.
Ce crible ne fonctionne que pour les petits nombres, c'est-à-dire ceux que l'on peut raisonnablement compter dans un temps fini ou mémoriser avec un ordinateur. Par contre, pour fabriquer un Nombre Premier de toutes pièces et de longueur arbitraire (pour créer une clé cryptographique par exemple), la seule technique à ma connaissance consiste à prendre un nombre impair au hasard, tester sa primalité et recommencer tout tant que le nombre est composé.
Cependant, il y a de moins en moins de chances de tomber sur un nombre premier lorsque le nombre à tester devient très grand, en raison de la raréfaction : la probabilité qu'un nombre n soit premier est approximativement égale à 1/ln(n). Pour un nombre entier de seulement 500 chiffres décimaux, cela correspond à une chance sur 1150 environ [6]. C'est donc un procédé non déterministe, avec un temps d'exécution aléatoire.
Les autres constructions mathématiques connues pour créer des nombres premiers ou P fonctionnent pour des sous-ensembles restreints (comme certains polynômes) ou bien de manière tellement lourde qu'un simple crible serait beaucoup plus efficace en place et/ou en temps de calcul [7]. Comme la suite de Nombres Premiers ne correspond à aucune progression linéaire, on s'imagine souvent qu'elle est pseudo-aléatoire, un mystérieux mélange d'ordre et de désordre...
1.3 Une autre approche basée sur les cribles
Les cribles (d'Ératosthène ou leurs évolutions) reposent sur une interprétation particulière de la définition des Nombres Premiers, ce qui ne nous éclaire pas du tout sur leur nature. En procédant par élimination, le crible d'Ératosthène nous renseigne sur ce que les Nombres Premiers ne sont pas (c'est-à-dire des nombres composés), mais pas sur ce qu'ils sont (ou leur structure). Cependant, en examinant l'algorithme du crible, nous pouvons entrevoir un début de solution. Il suffit de procéder un tout petit peu autrement, à commencer par l'utilisation d'une liste de nombres au lieu d'un tableau...
Pour reconstruire P, revenons à la liste complète des nombres entiers (N) :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ...
Nous allons toujours éliminer les nombres composés, à mesure que nous obtenons les nouveaux nombres premiers. Les nombres qui restent à chaque étape dans la liste, les candidats à la primalité qui seront éliminés ou non, sont aussi appelés « pseudo-premiers » ou « quasi-premiers ».
Au tout début, on remarque déjà que 0 et 1 ne sont pas considérés comme Premiers. Le premier nombre premier est logiquement 2. On le marque, puis on enlève un nombre sur deux pour éliminer tous les autres nombres pairs :
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35...
On remarque qu'on pourrait accélérer l'algorithme dès le début en initialisant la liste uniquement avec les nombres impairs... C'est-à-dire que la liste commencerait à 2, tous les éléments suivants ayant une valeur 2n+1.
Ensuite, on garde notre 2 comme Nombre Premier, et comme il n'a pas été éliminé, le nombre suivant (3) est aussi un Nombre Premier. On continue d'expurger notre liste en enlevant un nombre sur 3, ce qui élimine tous les multiples de 3.
2 3 5 7 (9) 11 13 (15) 17 19 (21) 23 25 (27) 29 31 (33) 35...
On obtient une nouvelle liste :
2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59...
Si on voulait initialiser directement cette liste, on créerait 2 et 3. Ensuite, chaque élément de la liste des Premiers serait égal au précédent, plus 2 ou 4 (en alternance). En JavaScript, cela donnerait typiquement :
var liste=new Array(); // liste des candidats à la primalité
function init_liste() {
var j=0; // index dans la liste
liste[j++]=2; // préremplit le début de la liste
liste[j++]=3;
var i=3; // dernier nombre premier connu;
// boucle principale
while (j < taille_de_la_memoire) {
i+=2;
liste[j++]=i;
i+=4;
liste[j++]=i;
}
}
Le prochain nombre de la liste est 5, qui est donc élevé au rang de Nombre Premier. Mais, ça se complique puisqu'il ne suffit plus d'enlever un nombre de la liste toutes les 5 positions. Les multiples de 5 commencent à être répartis un peu bizarrement, mais une présentation sur plusieurs lignes permet encore de discerner une structure répétitive :
2 3 5
7 11 13 17 19 23 (25) 29 31 (35)
37 41 43 47 49 53 (55) 59 61 (65)
67 71 ...
La différence entre des candidats successifs est cycliquement [4, 2, 4, 2, 4, 6, 2, 6]. Un moyen plus générique de créer la liste des candidats à la primalité s'impose. Voici donc une évolution du code précédent :
// définit les intervalles cycliques :
var cycle=new Array(4, 2, 4, 2, 4, 6, 2, 6);
// pré-initialise la liste des Premiers connus :
var liste=new Array(2, 3, 5);
function init_liste() {
var j=liste.length; // index dans la liste
var i=liste[j-1]; // dernier nombre premier connu;
var k=0; // index dans cycle
// boucle principale
while (j < taille_de_la_memoire) {
i+=cycle[k++]; // additionne le prochain intervalle
liste[j++]=i; // ajoute le nouveau candidat à la liste
if (k>=cycle.length)
k=0; // reboucle dans cycle
}
}
Comme vous pouvez l'imaginer, cet affinage pourrait être répété à volonté, ce qui nous affranchirait totalement de l'utilisation du crible d'Ératosthène pour éliminer les derniers nombres composés. Nous pouvons aisément obtenir un ensemble infini de candidats à la primalité, contenant de moins en moins de nombres composés, à condition de disposer d'un tableau cyclique suffisamment grand. Si cette amélioration du tableau cyclique est effectuée un nombre infini de fois, par exemple avec une Machine de Turing hypothétique, nous obtenons alors P.
1.4 Quelques idées pour un crible inverse
Pour l'instant, nous avons juste modifié l'algorithme d'Ératosthène en considérant l'ensemble des nombres entiers, dont nous enlevons progressivement les nombres que nous découvrons comme composés. Mais en fait, dans les morceaux de code déjà présentés, nous nous intéressons juste à l'amélioration de l'initialisation de la liste, et plus au crible lui-même. Pour la suite, nous ne retenons plus que deux éléments :
- D'abord, comme avec l'algorithme original, nous procédons progressivement en commençant par les premiers Nombres Premiers, qui sont mis dans une liste à part, au fur et à mesure de leur découverte. Le nombre 2 est oublié dès qu'il a servi à éliminer tous les nombres pairs. 3 disparaît dès que ses multiples sont enlevés, etc.
- Ensuite, au lieu d'avoir à traiter l'intégralité de l'ensemble des nombres Entiers, on pourrait réduire au strict nécessaire la quantité de nombres à mémoriser. On peut en fait se contenter du tableau cycle (contenant l'intervalle entre deux nombres candidats à la primalité), puisque les multiples des Nombres Premiers reviennent de manière prévisible, cyclique et régulière.
En fait, nous nous retrouvons maintenant avec juste deux structures : une sorte de pile où s'entassent les Nombres Premiers découverts, et un tableau cyclique d'intervalles (appelé simplement « cycle » par la suite). On peut complètement oublier les nombres composés éliminés, car nous allons uniquement créer un nombre premier à partir du précédent.
Comme cela fonctionne par construction plutôt que par élimination, l'algorithme que nous allons examiner s'appelle ici « crible inverse ». Il est apparenté aux algorithmes de cribles à roues [8][8'], étudiés et développés dans les années 1970 par Pritchard (entre autres). Notre structure cycle est équivalente à la roue des cribles à roues, mais il y a deux différences subtiles :
- Le cycle contient la différence entre deux pseudo-premiers, alors qu'une roue contient directement les pseudo-premiers.
- Une roue contient la valeur absolue des pseudo-premiers. Par contre, un cycle généré pour un nombre premier p est relatif à celui-ci, c'est-à-dire qu'il faut toujours ajouter un décalage de p pour obtenir la valeur des pseudo-premiers.
Ces deux différences de représentation sont importantes pour la suite, car elles mettent en évidence des phénomènes différents.
1.5 Etude et génération des intervalles entre Nombres Premiers consécutifs
Pour rappel, voici les 19 premiers Nombres Premiers ainsi que leurs intervalles :
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
1 1 2 2 4 2 4 2 4 6 2 6 4 2 4 6 6 2
A première vue, cela semble assez confus. Mais, en partant des observations précédentes, sous l'angle des cycles d'intervalles, nous allons y découvrir un ordre assez simple. La difficulté vient seulement du fait qu'il faut encore calculer N étapes avant d'obtenir le Nième Nombre Premier. On peut évidemment imaginer quelques astuces, mais c'est la simplicité de la structure, et non son efficacité, qui nous intéresse ici.
Comment passer de 1 à 2, de 2 à 3, de 3 à 5 et par extension de n'importe quel Premier au suivant, de manière identique ? Existe-t-il une relation de récurrence qui ne fait intervenir aucune donnée externe arbitraire ou probabiliste ? La réponse est « oui », mais nécessite de maintenir une donnée auxiliaire (le cycle) ; l'inconvénient est qu'il faut la connaître ou la reconstruire à partir de tous les Nombres Premiers précédents lorsqu'on veut calculer un Premier arbitraire.
C'est là qu'intervient une nouvelle technique qui transforme une liste cyclique en sa suivante, en fonction du dernier Nombre Premier découvert. Cela se passe en trois étapes : génération, réplication, puis combinaison [a].
- L'étape de génération crée un nouveau Nombre Premier : c'est simplement l'addition du précédent Premier et du premier élément de la liste cyclique. Cela correspond à l'étape du crible d'Ératosthène où on saute tous les nombres déjà éliminés pour sélectionner le nouveau Nombre Premier.
Premier += cycle[0].
- La liste cyclique est ensuite répliquée en fonction du résultat précédent. Par exemple, pour passer de 3 à 5, la liste cyclique de 3 ([2, 4]) est répliquée 5 fois (ce qui donne [2, 4, 2, 4, 2, 4, 2, 4, 2, 4]). Cette partie agit comme une multiplication.
- La combinaison doit effacer de la nouvelle liste les éléments qui donneraient des multiples du Nombre Premier fraîchement calculé. Lorsqu'un intervalle génère un nombre composé, cet intervalle est combiné avec le suivant (leurs valeurs sont ajoutées et réunies en un seul intervalle). Par exemple, pour la liste cyclique précédente, il faut effectuer deux combinaisons, car deux multiples de 5 apparaissent dans les sommes intermédiaires :
2
+ 4 = 6
+ 2 = 8
+ 4 = 12
+ 2 = 14
+ 4 = 18
+ 2 = 20 : multiple de 5, donc combiné pour donner 6
+ 4 = 24 (supprimé)
+ 2 = 26
+ 4 = 30 : multiple de 5
Dans cet exemple, la liste de 2×5=10 éléments ne contient plus que 8 éléments après combinaison, et aucun multiple de 5 ne sera généré.
En réalité, le code ne teste pas directement si le reste d'une division par 5 est nul. Il y a plus simple, si on tient compte du fait que les valeurs traitées sont souvent des petites valeurs : on fait des soustractions successives, et lorsque le résultat d'accumulation est nul, on combine les deux intervalles. On peut donc se passer totalement de multiplications, de divisions et de modulos. De plus, on peut fusionner l'étape de combinaison avec celle de la réplication afin de réduire le nombre total d'opérations et d'accès à la mémoire.
Les trois étapes doivent s'exécuter dans l'ordre indiqué, mais rien n'empêche a priori de commencer par l'une ou l'autre, à condition d'initialiser les variables correctement. Ici, je commence par la génération, car cela permet d'initialiser le système avec le minimum d'informations constantes.
L'étape de réplication génère toutes les combinaisons de multiples possibles et la combinaison élimine les intervalles tombant sur des multiples du nouveau Nombre Premier. L'analogie avec des franges d'interférences optiques est d'ailleurs intéressante.
Le dernier élément de la liste cyclique est combiné avec le premier élément ; ce dernier est enlevé du début pour tenir compte du fait qu'il vient d'être « consommé » lors de l'étape de génération. Sans cette opération qui fait office de rotation de la liste, la suite des nombres premiers ne progresserait pas...
En fait, le dernier élément de la liste cyclique est forcément combiné puisqu'il donne toujours un multiple du Nombre Premier que nous venons de calculer. De même, le premier élément de la liste cyclique (après rotation) n'est jamais combiné puisqu'il est pair, alors qu'on le compare avec un nombre premier impair.
On peut aller plus loin grâce à la parité, en observant que dès la troisième itération, tous les intervalles sont pairs et les premiers sont impairs. Or, un nombre impair doit être multiplié par deux pour qu'il puisse être congruent à un nombre pair. On en déduit qu'une combinaison d'intervalle ne peut se faire qu'une fois sur deux (au maximum), aux indices pairs du cycle.
La propriété de parité permet d'améliorer l'algorithme de combinaison en ne testant la congruence qu'une fois sur deux. Cependant, puisque l'algorithme publié ici commence avec 1, cette amélioration ne va pas être exploitée.
Si la combinaison ne peut avoir lieu qu'à un indice sur deux, cela signifie que la taille du cycle ne peut être divisée que par deux, au maximum, à chaque itération. En réalité, cela ne se produit qu'une fois lors de la première itération (le cycle [1,1] est combiné en [2]). Ensuite, après la réplication, la taille t(i) du i-ème cycle est égale à t(i-1)×p (où p est le nombre premier généré). Comme on n'élimine que les multiples de p, il y aura t(i-1) combinaisons, ce qui donne la taille finale :
t(i) = (p-1)×t(i-1)
Or, pour i>2, p est impair, donc p-1 est pair, donc t(i) est pair. En clair, un cycle a toujours une taille paire, dès la deuxième itération. C'est très utile à savoir, car cela peut simplifier le codage des conditions aux limites.
1.6 Exemple numérique
Pour bien comprendre les rouages de l'algorithme de crible inverse, il ne faut pas hésiter à effectuer les opérations à la main. En particulier, les premières itérations sont cruciales, et on s'aperçoit alors de la nécessité de l'introduction d'une variable temporaire.
Commençons par appliquer la méthode de génération-réplication-combinaison. Pour montrer qu'elle ne nécessite qu'une quantité très réduite d'informations, nous initialisons d'abord les deux listes avec juste le nombre p1=1 :
Premiers connus: p1=1
cycle : [p1=1]
- L'étape de génération donne un nouveau Nombre Premier p2=p1+cycle[0]=2.
- La réplication donne cycle=[1,1]
- La combinaison donne cycle=[2] puisque cycle[0]+cycle[1]=2=p2. cycle[0] et cycle[1] sont donc additionnés et remis dans cycle[0]. On obtient alors :
Premiers connus: p1=1, p2=2
cycle : [2]
Très bien, mais maintenant, comment passer de p2 à p3 qui devrait être égal à 3 ? 3-2=1 alors que la liste cyclique ne contient que 2. En fait, le 1 qui nous intéresse vient d'être « surécrit » par la combinaison précédente. Il aurait été possible d'éviter cela en décalant les indices de cycle et de traiter la dernière combinaison d'une manière spéciale, mais l'algorithme aurait perdu en lisibilité...
Ici, le choix a été fait de conserver la valeur précédente de cycle[0] dans une variable temporaire t. Elle est initialisée à p1 au tout début. Donc, nous avons en fait les opérations suivantes :
Premiers connus: p1=1
cycle : [1]
t = cycle[0]=1
génération : p2=p1+t=2
t=cycle[0]=1
réplication : cycle=[1,1]
combinaison : cycle=[2]
Ainsi, il est facile de passer à l'itération suivante :
Premiers connus: p1=1, p2=2
cycle : [2]
t=1
génération : p3=p2+t=2+1=3
t=cycle[0]=2
réplication : cycle=[2,2,2]
combinaison : cycle=[2,4]
et la suivante, et ainsi de suite...
Premiers connus: p1=1, p2=2, p3=3
cycle : [2,4]
t=2
génération : p4=p3+t=3+2=5
t=cycle[0]=2
réplication : cycle=[2,4,2,4,2,4,2,4,2,4]
combinaison : cycle=[4,2,4,2,4,6,2,6]
(premier signe de rotation effective)
Premiers connus: p1=1, p2=2, p3=3, p4=5
cycle : [4,2,4,2,4,6,2,6]
t=2
génération : p5=p4+t=5+2=7
t=cycle[0]=4
réplication : cycle=
[4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6,
4,2,4,2,4,6,2,6]
combinaison : cycle=
[ 2,4,2,4,6,2,6,
4,2,4, 6, 6,2,6,
4,2, 6, 4,6, 8,
4,2,4,2,4, 8, 6,
4, 6, 2,4,6,2,6,
6, 4,2,4,6,2,6,
4,2,4,2, 10,2,10 ]
En « retournant comme une chaussette » l'algorithme du crible d'Ératosthène, nous avons obtenu un algorithme récurrent (itératif) d'une complexité assez réduite (purement additif) et qui fonctionne lorsqu'il est initialisé à 1 (nous reviendrons sur ce point dans la partie 2.2).
1.7 Réalisation informatique
Pour résumer toutes ces discussions, voici une première version sous forme interprétable par votre navigateur web. Le code devrait fonctionner partout et pour les lecteurs qui ne sauraient utiliser du JavaScript. Je l'ai inclus dans une page HTML minimaliste.
Tous les exemples de cet article auraient pu être réalisés en pseudocode, comme je l'ai vu dans de nombreux papiers (les autres ne fournissent aucun code). Cependant, pour trouver plus facilement les erreurs, et surtout pour vérifier que cela fonctionne réellement, il vaut mieux le faire tourner sur une vraie machine (le bon vieux système papier-crayon-cerveau ayant des limites évidentes). Mais pourquoi utiliser JavaScript en particulier ?
D'abord parce que c'est un langage supporté universellement, à condition d'avoir un navigateur web. Ainsi, pas besoin d'installer un interpréteur ou compilateur Python, Perl, Ruby, C, Matlab, Octave, BASIC, ADA... Il suffit de diriger votre navigateur sur mon site (à http://ygdes.com/sources/premiers.html) pour voir le code fonctionner sous vos yeux. Si vous avez Firefox, l'extension Firebug vous aidera même à mieux comprendre ses rouages internes.
JavaScript est aussi un langage dynamique, interprété, avec un typage faible et assez peu de contraintes d'écriture, ce qui libère un peu l'esprit lorsqu'on code. On peut toujours réécrire le tout plus proprement ultérieurement, mais, au moins, lors de la mise en marche d'un algorithme, on peut se concentrer sur le problème au lieu de la syntaxe (qui est assez permissive). L'héritage de Scheme permet même d'utiliser certaines astuces ou techniques de codage avancées, mais ce n'est pas nécessaire ici.
JavaScript n'est pas un langage destiné aux calculs lourds ou complexes, mais la syntaxe proche du C facilite aussi la lecture et le portage. Et par rapport à du C plus rapide et efficace, il n'y a pas de code à ajouter pour la gestion dynamique de la mémoire (le ramasse-miettes intégré s'occupe de tout et économise du temps de développement). Enfin, l'intégration dans une page HTML permet de faire une présentation dynamique, plus attrayante, donc plus en phase avec la société lol-skyblog-myspace d'aujourd'hui, où l'information doit être fournie prédigérée et prête à être oubliée...
Il ne faut pas non plus oublier que les codes sources de cet article ont uniquement pour vocation de démontrer des principes, pas de les appliquer efficacement. D'ailleurs, la perspective est théorique, et non pratique : à quoi bon optimiser si le code est incompréhensible ?
<html><head>
<title>Générateur de nombres premiers</title>
</head><body bgcolor="white">
<script language="JavaScript" type="text/javascript">
var premier=1; // nombre premier en cours de traitement
var cycle=new Array(); // tableau qui va grossir
var premiers=new Array(); // liste des nombres premiers
var nb_premiers=0; // taille de la liste des premiers
premiers[nb_premiers++]=premier;
var taille_cycle=0; // ou cycle.length
cycle[taille_cycle++]=premier;
var t=premier; // variable temporaire
// affiche les variables pour le pas de calcul actuel
function affichage() {
var m='<p>Nombres premiers connus : '+premiers
+'<br>longueur du cycle : '+taille_cycle
+'<br>cycle : [ ';
var i=0;
while (i<taille_cycle) {
if (i<100)
m+=cycle[i++]+' ';
else {
m+=' ...';
break; // tronque l'affichage
}
}
document.write(m+'...]<p>');
}
/* création d'un nombre premier à partir
du nombre premier précédent et de son cycle */
function pas_direct() {
var i, j;
premier+=t; // crée le prochain Premier
t=cycle[0];
premiers[nb_premiers++]=premier;
var taille_nouveau_cycle=(premier-1)*(taille_cycle);
/* multiplication inutile car la même valeur peut être obtenue
à la fin de la double boucle principale, mais c'est pratique pour
savoir combien de place demander à malloc() ! (et d'autres bricoles) */
var nouveau_cycle=new Array(taille_nouveau_cycle);
var index_nouveau_cycle=-1; // préincrémenté, donc commencer à -1
var acc=0; // accumulateur pour compter le modulo
cycle[taille_cycle]=cycle[0]; // évite un off-by-one
// lors de la combinaison du dernier intervalle
// fabrique le nouveau cycle pour la prochaine itération
for(j=premier; j>0; j--) {
for (i=0; i<taille_cycle;) {
// modulo par soustractions successives
acc+=cycle[i++];
while (acc>=premier)
acc-=premier;
if (acc==0) // congruence ?
// combine avec l'élément précédent
nouveau_cycle[index_nouveau_cycle]+=cycle[i];
else
// simple recopie
nouveau_cycle[++index_nouveau_cycle]=cycle[i];
}
}
cycle=nouveau_cycle;
taille_cycle=taille_nouveau_cycle;
}
// Lance le calcul
affichage();
for (var i=0; i < 7; i++) {
pas_direct();
affichage();
}
</script></body></html>
Pour éviter la recopie du tableau cyclique, on pourrait coder une version « sur place » de l'algorithme. C'est possible parce que la combinaison des intervalles fait rétrécir la taille des cycles (dans l'exemple de p4, cycle passait de 10 éléments à la réplication, à 8 après la combinaison). Il faut toutefois effectuer la recopie en commençant par la fin, car la combinaison du cycle original empêcherait les autres cycles d'être correctement calculés. Mais, avant d'optimiser, il faut que l'algorithme fonctionne et soit facilement compréhensible. De plus, il consomme tellement de mémoire que cette optimisation n'a que peu d'importance...
On peut aussi économiser un bit de mémoire par nombre si on tient compte du fait que tous les intervalles (après la deuxième itération) sont pairs. Le bit peut être éliminé (par un décalage à droite), ou bien servir de drapeau, pour invalider l'élément par exemple. La liste cyclique d'intervalles peut donc servir plusieurs fois, et des combinaisons supplémentaires peuvent être effectuées sans modifier l'intégralité du cycle.
1.8 Comportement à l'exécution
L'affichage de la page HTML devrait donner le résultat suivant :
Nombres premiers connus : 1
longueur du cycle : 1
cycle : [ 1 ]
Nombres premiers connus : 1,2
longueur du cycle : 1
cycle : [ 2 ]
Nombres premiers connus : 1,2,3
longueur du cycle : 2
cycle : [ 2 4 ]
Nombres premiers connus : 1,2,3,5
longueur du cycle : 8
cycle : [ 4 2 4 2 4 6 2 6 ]
Nombres premiers connus : 1,2,3,5,7
longueur du cycle : 48
cycle : [ 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4
2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 ]
Nombres premiers connus : 1,2,3,5,7,11
longueur du cycle : 480
cycle : [ 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2
4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4 6
2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4 6 2 6 6
4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2 4 12 2 6 4 ...]
Nombres premiers connus : 1,2,3,5,7,11,13
longueur du cycle : 5760
cycle : [ 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4
14 4 6 2 10 2 6 6 4 6 6 2 10 2 4 2 12 12 4 2 4 6 2 10
6 6 6 2 6 4 2 6 4 14 4 2 4 6 8 6 10 2 4 6 2 6 6 6 4 6
2 6 4 8 10 2 10 2 4 2 4 6 8 4 2 4 12 8 4 2 6 4 6 12 2
4 2 ...]
Nombres premiers connus : 1,2,3,5,7,11,13,17
longueur du cycle : 92160
cycle : [ 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14
4 6 2 10 2 6 6 4 6 6 2 10 2 4 2 12 12 4 2 4 6 2 10 6 6
6 2 6 4 2 10 14 4 2 4 14 6 10 2 4 6 2 6 6 6 4 6 8 4 8 10
2 10 2 4 2 4 6 8 4 2 4 12 8 4 8 4 6 12 2 6 12 6 4 6 6 6 ...]
Comme les nombres de JavaScript sont au format IEEE756 64 bits, et en tenant compte des structures internes de gestion des données, un nombre occupe environ 10 octets dans Mozilla. En conséquence, le cycle de 92160 intervalles ci-dessus utilise environ 1Mi octets (on peut faire beaucoup mieux en C en utilisant des octets). En poussant un peu le nombre d'itérations, la quantité de mémoire explose littéralement :
Nombres premiers connus : 1,2,3,5,7,11,13,17,19
longueur du cycle : 1658880
cycle : [ 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4
6 2 10 2 6 6 4 6 6 2 10 2 4 2 12 12 4 2 4 6 2 10 6 6 6
2 6 4 2 10 14 4 2 4 14 6 10 2 4 6 8 6 6 4 6 8 4 8 10 2
10 2 6 4 6 8 4 2 4 12 8 4 8 4 6 12 2 6 12 6 10 6 6 2 6
10 6 ...]
Nombres premiers connus : 1,2,3,5,7,11,13,17,19,23
longueur du cycle : 36495360
cycle : [ 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6
2 10 2 6 6 4 6 6 2 10 2 4 2 12 12 4 2 4 6 2 10 6 6 6 2
6 4 2 10 14 4 2 4 14 6 10 2 4 6 8 6 6 4 6 8 4 8 10 2 10
2 6 4 6 8 4 2 4 12 8 4 8 4 6 12 2 18 6 10 6 6 2 6 10 6 6 2 ...]
Avec plus de 36 millions de nombres, le navigateur a besoin de 400Mi octets de RAM pour seulement 9 itérations. Si on essayait d'exécuter cette page avec 10 itérations, l'occupation atteindrait environ 10Gi octets.
Pour faire tourner la page HTML/JavaScript jusqu'à 9 itérations, cela prend aussi beaucoup de temps, même avec un ordinateur récent. Le navigateur va l'interrompre plusieurs fois avant qu'il ne termine son travail. Pour cela, si vous voulez jouer avec sous Firefox, je suggère de modifier dans about:config le paramètre dom.max_script_run_time, pour le porter à 40, 60 secondes ou même plus. Cela va être d'ailleurs utile pour refaire tourner l'algorithme, doté cette fois-ci de code qui mesure et affiche le comportement précis (qualitatif et quantitatif) de l'algorithme.
Si on regarde la croissance de la somme des intervalles du cycle à chaque itération, on retrouve une progression primorielle (notée #) [9] : c'est comme une factorielle (notée !), mais au lieu de multiplier tous les nombres entiers entre eux (2×3×4×5×6×7...), on multiplie tous les nombres premiers entre eux (2×3×5×7×11×13...). C'est aussi cohérent avec le comportement des cribles à roues.
La croissance du nombre d'intervalles d'un cycle (étudiée dans la partie 1.5) n'obéit pas à la même progression : elle est sous-primorielle, car tous les nombres multipliés entre eux sont des premiers moins 1. Par exemple, pour passer de 8 nombres à 48, il faut multiplier la taille du cycle par 6, c'est-à-dire le nombre premier 7 que l'on vient de calculer, moins un. Cette progression est connue comme la séquence A005867 de l'OEIS [10] et décrite comme la série des minimums locaux de la fonction Phi d'Euler. Elle est déjà utilisée dans la théorie des cribles.
nombre produit des taille du
généré nombres cycle
premier primorielle sous-primorielle
p p# EulerPhi(p#)
2 2 1×(2-1)=1
3 2×3=6 1×(3-1)=2
5 6×5=30 2×(5-1)=8
7 30×7=210 8×(7-1)=48
11 210×11=2310 48×(11-1)=480
13 2310×13=30030 480×(13-1)=5760
17 30030×17=510510 5760×(17-1)=92160
19 510510×19=96996990 92160×(19-1)=1658880
23 96996990×23=223092870 1658880×(23-1)=36495360
Cette consommation monstrueuse d'espace mémoire explique certainement pourquoi, bien que cet algorithme a déjà été découvert (sous une forme ou une autre), il n'a pas semblé intéressant, il est donc resté dans les cartons... Le crible d'Ératosthène est en effet, à utilisation de mémoire égale, plus efficace que cet algorithme assez brutal. Toutefois, puisque les intervalles restent des nombres de valeur modeste (l'écart moyen entre un premier p et le suivant est ln(p)), le stockage nécessaire est réduit pour les très grands nombres.
2. Propriétés et analyse de l'algorithme
2.1 Exhaustivité de l'algorithme
Nous avons vu que le crible inverse est dérivé directement du crible d'Ératosthène, dont il est un corollaire ou une réciproque. Cependant, peut-on s'assurer que l'algorithme génère bien tous les Nombres Premiers, et seulement ceux-ci ? Le crible inverse est dérivé du crible standard, bien connu pour générer correctement les Nombres Premiers, mais la transformation pourrait avoir introduit une erreur. Pour vérifier qu'il fonctionne correctement, nous allons examiner une itération du crible inverse, c'est-à-dire les opérations de génération-réplication-combinaison qui transforment un nombre premier et son cycle, en un autre nombre premier et son cycle.
- D'abord, une itération de l'algorithme doit commencer avec un nombre premier, et non un nombre composé, sinon les prochains résultats seront d'autres nombres composés. Cela est dû à l'étape de génération, où le nombre premier précédent est ajouté au premier nombre du cycle précédent. Si un nombre composé était considéré comme premier par l'algorithme, cela introduirait un décalage dans les prochaines itérations, entraînant la génération d'autres nombres composés.
- De plus, le nouveau nombre premier généré agit sur le calcul du cycle, et si un nombre composé s'immisce, le cycle aura la mauvaise taille et un mauvais contenu, ce qui provoquera nécessairement l'apparition d'autres nombres composés dans les itérations suivantes. De même, si le cycle est altéré ou mal calculé, donc s'il contient des intervalles non valides, les prochaines itérations de l'algorithme généreront tôt ou tard des nombres composés.
- Aussi, les nombres premiers générés sont bien successifs, en raison de la nature additive de l'étape de génération et de combinaison. Les nombres premiers sont la somme du précédent nombre premier et du premier élément du cycle : puisqu'ils sont tous positifs, leur somme est forcément positive. Puisque la liste des nombres premiers générés ne peut pas devenir décroissante ou même stagner, ce sont donc bien des nombres premiers successifs.
En fait, en raison de la simplicité de l'algorithme, on s'apercevrait facilement et rapidement si un nombre composé ou invalide était généré par le crible inverse. Mais, comme les propriétés d'une itération sont bien définies (un nombre premier en entrée donne le prochain nombre premier en sortie, un nombre composé en entrée donne tôt ou tard un nombre composé en sortie), on peut utiliser une démonstration par récurrence. Et, lorsqu'on regarde les premières itérations de l'algorithme, on voit que les résultats sont corrects (au moins jusqu’à 23) donc les itérations suivantes donneront aussi un nombre premier.
2.2 Primalité du nombre 1
La petite démonstration précédente indique que pour obtenir un nombre premier, il faut que le nombre précédemment généré soit premier. Dans l'algorithme décrit dans la première partie, nous initialisons les données à 1. Cela implique que 1 est premier. Et là, c'est la catastrophe.
Il existe de nombreux arguments pour et contre la primalité du nombre 1 [11] [12] [13]. Il est communément admis que 1 n'est pas un Nombre Premier pour des raisons de facilité et de démonstration, comme la FAQ du groupe fr.sci.math sur Usenet [2] l'explique clairement :
A noter que la définition de nombre premier exclut 1. Admettre 1 comme nombre premier rendrait faux l'important Théorème fondamental de l'arithmétique qui dit qu'il existe une unique manière d'écrire un nombre entier supérieur à 1 comme produit de nombres premiers (sans prendre en compte l'ordre de la multiplication).
Pourtant, 1 est l'élément neutre de l'arithmétique puisque 1×1=1. Je dirais même plus : comme 1 sert à amorcer le crible inverse, c'est le Premier Premier, la « graine » qui permet de construire les autres nombres, d'une manière ou d'une autre... Cette conviction se renforce si on initialise l'algorithme avec un autre nombre : par exemple, si on commence avec 2, il n'est pas possible de passer à 3 ! [b]
Toujours selon [12], T. Gowers aurait écrit :
« The seemingly arbitrary exclusion of 1 from the definition of a prime does not express some deep fact about numbers: it just happens to be a useful convention, adopted so there is only one way of factorizing any given number into primes » [c]
En fait la solution au dilemme est simple : il suffit d'élargir un peu la propriété d'une itération de crible inverse, en incluant le nombre 1. Cela donne alors :
Une itération de l'algorithme doit commencer avec un nombre premier ou 1, et non un nombre composé.
Ou mieux, puisque 1 n'est pas composé :
Une itération de l'algorithme ne doit pas commencer avec un nombre composé.
Voilà. Maintenant que ce point de dialectique est écarté, nous pouvons commencer à exploiter les propriétés de l'algorithme.
2.3 Persistance des intervalles
Le crible inverse ne travaille pas directement sur les nombres premiers, mais sur l'intervalle séparant les premiers consécutifs [d]. Tout amateur de Mathématiques y reconnaîtra une opportunité pour étudier les nombreuses questions qui ont été posées à ce sujet [14], comme le postulat de Bertrand [15] (en fait un théorème), la conjecture de Legendre [16] ou tout simplement la conjecture des Nombres Premiers Jumeaux [17]. Cette dernière est d'ailleurs la plus connue, la plus intéressante et probablement la plus facile à aborder avec le crible inverse.
Selon cette conjecture, il existerait une infinité de nombres premiers p pour lesquels p-2 est aussi premier. Or, nous avons vu que pour fabriquer le n-ième nombre premier, il faut effectuer n itérations de génération-réplication-combinaison. Et, pour générer une paire de nombres premiers jumeaux, il faut que le nombre 2 arrive en première position dans le cycle, où il sera utilisé pour générer le deuxième jumeau. Dans la partie 1.8, cela se voit directement lorsque le crible inverse génère les nombres 5, 7 ou 13...
2.3.1 Aspect quantitatif
A priori, la génération d'une paire de premiers jumeaux par le crible inverse dépend donc de la disponibilité du nombre 2 au début du cycle. Pour être vraie, la conjecture implique déjà que le nombre 2 sera toujours présent dans le cycle, à n'importe quelle itération. Si 2 disparaissait du cycle à un moment ou un autre, la conjecture deviendrait fausse. Une approche de type producteur-consommateur va nous aider à déterminer le taux de croissance de cet intervalle, pour quantifier sa raréfaction ou prédire une éventuelle disparition.
- Le producteur est l'étape de réplication. Lors d'une itération, le nombre d'intervalles égaux à 2 est multiplié par le nombre premier qui vient d'être généré.
- Le consommateur est l'étape de combinaison qui réduit le nombre d'éléments du cycle. Nous avons vu dans les parties 1.5 et 1.8 que le nombre de combinaisons est égal à la taille du cycle précédent, entraînant la progression en EulerPhi(p#) de l'espace nécessaire en mémoire.
La génération ne consomme pas de nombre dans le cycle, car la valeur additionnée au nombre premier précédent est simplement recopiée du début du cycle. Cette valeur est aussi déplacée à la fin pour être combinée et effectuer la rotation.
Une partie de l'étude porte sur l'étape de combinaison dont nous allons déterminer les propriétés, mais, dans un premier temps, on peut déjà examiner la condition à la limite : nous allons supposer que la conjecture est fausse, ce qui impliquerait que, à un moment, tous les 2 disparaîtraient de cycle en une itération.
- S'il ne subsistait qu'un seul 2 dans cycle après une combinaison, alors ce 2 serait répliqué p fois dans l'itération suivante (p étant le nombre premier généré dans la nouvelle itération).
- Si la combinaison suivante devait éliminer tous les 2 de cycle, cela impliquerait que p serait lui-même égal à (ou multiple de) 2. Or, c'est impossible par construction, car un nombre ne peut être généré qu'une seule fois et, par définition, ses multiples ne sont pas premiers.
Par exemple, lors de la génération du nombre 5 à partir de 3, le cycle [2,4] est répliqué pour donner [2,4,2,4,2,4,2,4,2,4]. Pour enlever tous les 2, il faudrait que p soit égal à 2, 3 ou 6. Or, c'est impossible puisque 2 et 3 ont déjà été générés, et que 6 étant multiple des deux nombres précédents, il a donc déjà été éliminé par une étape de combinaison. Dans le cas contraire, l'algorithme ne pourrait pas générer tous les nombres premiers.
Nous allons maintenant quantifier les intervalles égaux à 2 dans cycle. En modifiant le programme de la partie 1.7, on peut mesurer l'évolution du nombre de 2 lors des premières itérations de l'algorithme.
nombre premier généré 2 3 5 7 11 13 17 19 23
nombre de 2 après réplication 0 3 5 21 165 1755 25245 423225 8709525
nombre de 2 combinés 0 2 2 6 30 270 2970 44550 757350
nombre de 2 après combinaison 0 1 3 15 135 1485 22275 378675 7952175
ratio combinés/répliqués * 0,666 0,4 0,2857 0,1818 0,1538 0,11764 0,10526 0,08695
longueur du cycle 1 2 8 48 480 5760 92160 1658880 36595360
proportion de 2 dans cycle 1 0,5 0,375 0,3125 0,28125 0,2578 0,24169 0,22827 0,21789
On voit apparaître d'autres séquences qui sont déjà connues, ce qui permet de trouver ou déduire les formules qui les régissent :
- La quatrième ligne (0 1 3 15 135...) est semblable à EulerPhi(p#) et connue comme A059861 [10']. C'est tout simplement le produit des nombres premiers générés, mais au lieu de soustraire 1 à chaque nombre, on soustrait 2 : p(i)-2 × p(i-1)-2 × ... × p(1)-2.
- La deuxième ligne (0 3 5 21 165...) n'est pas référencée, mais on sait que, par construction, c'est la valeur de la quatrième ligne de la colonne précédente, multipliée par le nombre premier généré, soit p(i) × p(i-1)-2 × p(i-2)-2 × ... × p(1)-2.
- La troisième ligne (0 2 2 6 30 270...) correspond à A121406 [10'']. C'est la différence entre les lignes 2 et 4, soit 2×Π(p(i-1)-2). C'est donc aussi le double de la colonne précédente de la quatrième ligne, ce qui signifie qu'une itération combine deux fois plus de 2 qu'il n'y en avait dans l'itération précédente.
- Le rapport entre les lignes 2 et 3 est simplifiable à 2/p(i), qui tend vers 0 lorsque i augmente. Cela indique que les 2 sont répliqués plus vite qu'ils ne sont combinés.
Conclusion : il y aura toujours dans cycle des 2 pour générer, à un moment ou un autre, des nombres premiers jumeaux.
2.3.2 Aspect statistique
Il ne suffit pas de montrer que les intervalles sont conservés, il faut aussi que ces intervalles puissent se retrouver au début de cycle pour donner naissance à une paire de jumeaux. Il faut donc étudier où et comment les combinaisons ont lieu.
Imaginons une hypothèse de conspiration des nombres : si les combinaisons se produisaient plus au début de cycle, alors, après d'innombrables itérations, il y aurait peu de chances qu'un 2 parvienne à se décaler jusqu'au début pour générer un nombre premier jumeau. Leur abondance ne suffirait pas à compenser une plus forte densité locale de combinaisons.
Il semble cependant que les combinaisons sont réparties équitablement dans cycle. A partir du programme de la partie 1.7, j'ai généré le tableau suivant, qui est l'histogramme des indices de cycle où ont lieu les combinaisons.
premier : 2 3 5 7 11 13 17 19 23
bin 0/8 : 1 0 0 0 5 60 719 11519 207359
bin 1/8 : 0 0 0 1 7 59 720 11520 207361
bin 2/8 : 0 0 0 1 6 60 720 11520 207359
bin 3/8 : 0 0 0 1 5 60 720 11520 207360
bin 4/8 : 0 1 0 2 6 60 721 11521 207360
bin 5/8 : 0 0 1 1 6 61 720 11520 207360
bin 6/8 : 0 0 0 0 6 59 719 11519 207361
bin 7/8 : 0 0 1 2 7 61 721 11520 207360
A chaque fois que le programme combine un intervalle avec le précédent, l'index de l'intervalle est normalisé pour servir d'adresse dans le tableau, où la case correspondante est incrémentée. J'ai choisi un histogramme à 8 cases de tailles identiques (« bins ») afin de retrouver les valeurs 1 dans la colonne correspondant au nombre premier 7.
A cause de l'utilisation de JavaScript, la normalisation a été réalisée avec une division en nombres flottants qui a semble-t-il introduit quelques erreurs d'arrondis. Pourtant, dans chaque colonne, on retrouve non seulement des valeurs quasiment égales, mais leur somme correspond bien à la taille du cycle correspondant (ce qui confirme que le programme ne contient pas d'erreur flagrante).
Si les combinaisons des intervalles égaux à 2 (qui empêchent de générer les paires de premiers jumeaux) se produisent à des endroits statistiquement équidistants sur l'ensemble du cycle, alors la probabilité qu'une paire de jumeaux soit générée par une itération du crible inverse est proportionnelle au rapport entre la taille du cycle et le nombre de 2 qu'il contient. Ce rapport est égal à Π(p(i)-2)/Π(p(i)-1) et tend vers 0 quand i augmente, mais ne sera jamais égal à 0.
Ce n'est pour l'instant qu'une ébauche de démonstration qui va encore demander du travail, car le paragraphe précédent contient un gros si. Mais, son principe peut être généralisé à tout intervalle pair autre que 2, ce qui résoudrait aussi la conjecture de De Polignac [18]. On peut même aller plus loin en généralisant l'idée à tout type de séquence d'intervalle (on parle alors de « constellations », qui font aussi l'objet de conjectures).
2.4 Autres conséquences
L'analyse du crible inverse peut donner d'autres résultats intéressants en Théorie des Nombres. Parmi les conjectures qui pourraient bénéficier de cette étude, on pense naturellement à la conjecture de Goldbach [19], puisqu'il s'agit aussi uniquement d'additions. Tout porte à croire que tous les nombres entiers pairs (supérieurs à 2) sont la somme de deux nombres premiers (l'équivalent additif de la génération des nombres entiers par la multiplication de nombres premiers). Une autre manière d'exprimer ceci est que tout nombre entier est la moyenne de deux nombres premiers.
Après avoir résolu les conjectures des nombres premiers jumeaux et de Goldbach, on peut ensuite s'intéresser aux autres problèmes de Landau [20] [21], la conjecture de Legendre [16] et celle des carrés parfaits.
Conclusion
Cet article a présenté une méthode simple, peu utile en pratique mais aux aspects théoriques intéressants, pour générer la suite des Nombres Premiers. Elle confirme, s'il était nécessaire, que l'ensemble des Nombres Premiers n'est pas du tout aléatoire ni même terriblement complexe. Elle est proche de certaines méthodes existantes, mais, grâce à quelques différences, il devient possible d'aborder sous un nouveau jour des conjectures réputées très difficiles, sans recourir à un arsenal d'outils extrêmement élaborés.
J'espère ainsi avoir aiguillonné votre curiosité et peut-être même fait découvrir certains aspects de la Théorie des Nombres. Il reste pourtant de nombreuses questions dont les réponses sont hors de ma portée. Les prochaines années s'annoncent donc très excitantes, non seulement pour l'avancée des théories, mais aussi sur la manière de les traiter (sur le plan technique comme humain). Je souhaite que d'autres personnes puissent utiliser les approches de cet article pour démontrer formellement d'autres conjectures, après avoir trouvé des failles éventuelles dans mes raisonnements.
Je tiens finalement à remercier toutes les personnes qui m'ont soutenu et encouragé à rédiger cet article, à commencer par Laura, Bernard, Emmanuel, Guy, Henri, Mark, Christian, l'équipe des éditions Diamond... De nombreuses autres personnes l'ont aussi relu ou contribué à l'améliorer, directement ou indirectement.
Notes
[a] Le terme « combinaison » est tout ce que j'ai pu trouver pour décrire l'opération. D'autres termes candidats comme « liaison », « fusion », « criblage », « modulo » ou « interférence » me semblent convenir encore moins.
[b] Que se passerait-il si on initialisait l'algorithme avec des données différentes ? Quelles seraient les propriétés des suites ainsi générées ? Il reste tellement de choses à explorer !
[c] « L'exclusion apparemment arbitraire du nombre 1 de la définition des nombres premiers n'est pas l'expression d'un quelconque fait fondamental à propos des nombres : il se trouve juste que c'est une convention utile, adoptée afin qu'il n'y ait qu'une seule façon de factoriser n'importe quel nombre. »
[d] Attention toutefois à ne pas confondre les intervalles entre les nombres premiers et les intervalles du cycle ! Une partie de ces derniers sera éliminée après une ou plusieurs étapes de combinaison, ce qui va être très important par la suite.
Liens
Malgré la profusion de sites web dédiés aux Nombres Premiers, on ne peut pas passer à côté de Wikipédia :
[1] http://fr.wikipedia.org/wiki/Nombre_premier
[2] La Foire Aux Questions du newsgroup fr.sci.maths : http://faq.maths.free.fr/texte/faq51.html
[3] http://fr.wikipedia.org/wiki/Test_de_primalité_de_Miller-Rabin
[3'] Test de primalité de Miller-Rabin par exponentiations successives : http://cermics.enpc.fr/polys/oap/node91.html
[4] http://fr.wikipedia.org/wiki/Test_de_primalité_de_Solovay-Strassen
[5] http://fr.wikipedia.org/wiki/Crible_d'Ératosthène
[6] http://www.bibmath.net/crypto/complements/gdspremiers.php3
[7] http://mathworld.wolfram.com/PrimeFormulas.html
[8] http://en.wikipedia.org/wiki/Wheel_factorization
[8'] « Le crible de la roue en distribué » (Gabriel Paillard, Christian Lavault)
[9] http://fr.wikipedia.org/wiki/Primorielle
[10] La séquence A005867 (EulerPhi(p#)) de l'OEIS (Encyclopédie en ligne des séquences de nombres) http://www.research.att.com/~njas/sequences/A005867
[10'] La séquence A059861 (Π(p(i)-2)) http://www.research.att.com/~njas/sequences/A059861
[10''] La séquence A121406 http://www.research.att.com/~njas/sequences/
[11] « Why is the number one not prime? » : http://primes.utm.edu/notes/faq/one.html
[12] http://en.wikipedia.org/wiki/Prime_number#Primality_of_one
[13] « Arguments for and against the primality of 1 » : http://www.geocities.com/primefan/Prime1ProCon.html
[14] http://en.wikipedia.org/wiki/Prime_gap
[15] http://en.wikipedia.org/wiki/Bertrand%27s_postulate
[16] http://fr.wikipedia.org/wiki/Conjecture_de_Legendre
[17] http://en.wikipedia.org/wiki/Twin_prime_conjecture
[18] http://en.wikipedia.org/wiki/De_Polignac's_conjecture
[19] http://fr.wikipedia.org/wiki/Conjecture_de_Goldbach
[20] http://en.wikipedia.org/wiki/Landau's_problems
http://hal.archives-ouvertes.fr/docs/00/02/96/29/PDF/CribleRoue.pdf
[21] Les 4 problèmes de Landau : http://mathworld.wolfram.com/LandausProblems.html
[22] Les nombres premiers jumeaux et une relation éventuelle avec la conjecture de Goldbach : http://mathworld.wolfram.com/TwinPrimes.html
[23] On peut encore trouver en ligne certains travaux de Paul Pritchard : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.835
[24] Les recherches de la famille Lifshitz : http://www.primenumbers.net/
[25] Le site de Chris Caldwell à l'Université du Tenessee à Martin : http://primes.utm.edu
[26] La page personnelle du mathématicien Jean-Paul Delahaye contient certains des articles qu'il écrit régulièrement pour le magazine Pour La Science : http://www2.lifl.fr/~delahaye/
[27] Le programme JavaScript de génération de nombres premiers est aussi disponible à : http://ygdes.com/sources/premiers.html
