|
Édition du: 30/10/2021 |
|
INDEX Nombres
(Classification) |
CRIBLES (Sieves) |
|||
|
TYPES de CRIBLES
Le crible
arithmétique le plus connu est celui d'Ératosthène, celui qui permet
d'atteindre tous les nombres premiers. Il en existe
bien d'autres qui fonctionnent aussi par élimination et parfois en mobilisant
une opération particulière. D'une
manière générale, un crible est utilisé pour trier une catégorie de nombres
ou pour en calculer la quantité. Méthode de tri par élimination.
Discrimination de nombres ayant une certaine propriété. En
théorie moderne, les cribles font appel à des fonctions qui discriminent
majoritairement sur l'ensemble et minoritairement en dehors. Le but étant de
trouver une fonction plus facile à analyser que la fonction caractéristique
habituelle de l'ensemble. |
||
|
|
Sommaire de cette page >>> Cribles des nombres premiers >>> Cribles pour autres catégories de nombres >>> Cribles produisant des nombres chanceux >>> Théorie des cribles |
Débutants Glossaire |
|
Ératosthène |
La sortie
du crible est la suite des nombres premiers. |
|
|
Sudaram |
La sortie
du crible est la suite des nombres premiers. |
|
|
Helfgott |
Produit
les nombres premiers et la factorisation des nombres composés. Intérêt:
réduit la taille des mémoires. |
|
|
Legendre |
Crible destiné
au calcul de la quantité de
nombres premiers. |
|
|
Brun* * niveau avancé non traité sur ces pages |
Crible du
type de celui d'Ératosthène, mais plus puissant. Brun pionnier de la formalisation
de la théorie des cribles. |
|
|
Atkin* |
Version
améliorée du crible d'Ératosthène créée en 1999 – Utilisation de formes
quadratiques binaires comme 4x² + y² = p. |
|
|
Moessner |
Il
engendre les puissances des nombres, les factorielles des nombres, etc. |
|
|
Congruences |
Transforme
la suite des nombres en une suite réduite cyclique. |
|
|
Mian-Chowla |
Race de
nombres qui se construisent en considérant les sommes inférieures à chacun
d'eux. |
|
|
Quadratique* * niveau avancé non traité sur ces pages |
Utilisé pour
la factorisation de grands nombres. Basé sur l'arithmétique modulaire
(congruences) du type x² ≡ y² mod n |
|
|
Pollard** |
Méthode p
– 1 de Pollard: factorisation hyper rapide |
|
|
Corps de nombres généralisé** |
Un des
algorithmes les plus efficaces pour la factorisation de tr-s grands nombres. |
|
|
Selberg** |
Crible de
type combinatoire impliquant un système de poids optimisés pour s'adapter au
problème posé. |
|
|
Formule du crible* Formule de Poincaré |
Dénombrer
une réunion de n ensembles non nécessairement disjoints |
|
Anglais: Number Field Sieve
|
Flavius Josèphe |
Problème d'élimination
des soldats de sorte que celui qui choisit soit le dernier. |
|
|
Euler |
Il
produit les nombres chanceux d'Euler. |
|
|
Ulam |
Il produit
les nombres chanceux d'Ulam. |
|
|
Chanceux par plages |
Il
produit une autre catégorie de nombres chanceux. |
|
|
Branche de la théorie des nombres qui
s'attache à formaliser les procédés de tri par crible notamment des nombres
premiers. Un des pionniers fut Viggo Brun (1885-1978) qui formalisa la
théorie des cibles. Résultat célèbre: la somme des inverses des
nombres premiers jumeaux est convergente: constante de Brun. |
Anglais: Sieve theory
Commentaires – Langues
|
Le crible est synonyme de tamis, de passoire. Le
chercheur d'or utilise une batée. Sieve, en anglais, est une passoire, un tamis. Sierpinski sieve or Sierpinki gasket: fractale de
Sierpinski. |
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
