In the field of number theory, the Brun sieve (also called Brun's pure sieve) is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others.
In terms of sieve theory the Brun sieve is of combinatorial type; that is, it derives from a careful use of the inclusion–exclusion principle.
Let be a finite set of positive integers.
Let be some set of prime numbers.
For each prime in , let denote the set of elements of that are divisible by .
This notation can be extended to other integers that are products of distinct primes in . In this case, define to be the intersection of the sets for the prime factors of .
Finally, define to be itself.
Let be an arbitrary positive real number.
The object of the sieve is to estimate:
where the notation denotes the cardinality of a set , which in this case is just its number of elements.
Suppose in addition that may be estimated by
where is some multiplicative function, and is some error function.
Let
This formulation is from Cojocaru & Murty, Theorem 6.1.2. With the notation as above, suppose that
for any squarefree composed of primes in ;
for all in ;
There exist constants such that, for any positive real number ,
Then
where is the cardinal of , is any positive integer and the invokes big O notation.
In particular, letting denote the maximum element in , if for a suitably small , then
Brun's theorem: the sum of the reciprocals of the twin primes converges;
Schnirelmann's theorem: every even number is a sum of at most primes (where can be taken to be 6);
There are infinitely many pairs of integers differing by 2, where each of the member of the pair is the product of at most 9 primes;
Every even number is the sum of two numbers each of which is the product of at most 9 primes.
The last two results were superseded by Chen's theorem, and the second by Goldbach's weak conjecture ().
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
En mathématiques, la théorie des cribles est une partie de la théorie des nombres ayant pour but d'estimer, à défaut de dénombrer, les cardinaux de sous-ensembles (éventuellement infinis) de N en approchant la fonction indicatrice du sous-ensemble considéré. Cette technique a pour origine le crible d'Ératosthène, et dans ce cas, le but était d'étudier l'ensemble des nombres premiers. Un des nombreux résultats que l'on doit aux cribles a été découvert par Viggo Brun en 1919.
vignette|ce schéma représente la théorie Le théorème de Brun énonce la convergence de la série des inverses des nombres premiers jumeaux. Sa somme est appelée constante de Brun. Autrement dit la somme (où désigne l'ensemble des nombres premiers) est finie. Le mathématicien norvégien Viggo Brun restera dans les mémoires comme étant l'inventeur des méthodes modernes de cribles combinatoires. Entre 1917 et 1924, il inventera et perfectionnera cette théorie, dont le principe repose sur le crible d'Ératosthène.
Viggo Brun est un mathématicien norvégien né le à Lier et mort le à Drøbak. Il est essentiellement connu comme étant le créateur d'une méthode de crible (le ), inspirée de celle d'Ératosthène, mais plus puissante. Un des résultats célèbres de cette méthode est que la somme des inverses des nombres premiers jumeaux est convergente. En son honneur, on a défini la somme de cette série comme étant la constante de Brun. Théorème de Brun Viggo Brun, Le crible d'Eratosthène et le théorème de Goldbach, Kristiania,
Explore les tests de bonté d'ajustement, les tests X2 et les tests d'indépendance dans les statistiques, avec des exemples pratiques et des applications.
In this paper we exhibit the full prime factorization of the ninth Fermat number F9 = 2(512) + 1. It is the product of three prime factors that have 7, 49, and 99 decimal digits. We found the two largest prime factors by means of the number field sieve, wh ...
We show that the prime divisors of a random polynomial in F-q[t] are typically "Poisson distributed". This result is analogous to the result in Z of Granville [1]. Along the way, we use a sieve developed by Granville and Soundararajan [2] to give a simple ...
2009
, ,
On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factori ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa1999