Namespaces
Variants
Actions

Difference between revisions of "Brun sieve"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (TeX encoding is done)
 
Line 1: Line 1:
A [[Sieve method|sieve method]] in elementary number theory, proposed by V. Brun [[#References|[1]]]; it is an extension of the sieve of Eratosthenes (cf. [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). The method of Brun's sieve may be described as follows. Out of a sequence of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177001.png" /> the numbers with small prime divisors are eliminated ( "sieved out" ) leaving behind prime and almost-prime numbers (cf. [[Almost-prime number|Almost-prime number]]) with only large prime divisors. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177002.png" /> be the amount of these numbers. It can be shown that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177003.png" /> is included between two sums with a relatively-small number of summands, which may be estimated from above and from below. Thus, it is possible to evaluate from above the number of [[Twins|twins]] in a given interval. Brun's sieve is employed in additive number theory. Brun used his sieve to prove that all large even numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177004.png" /> can be represented in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177005.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177006.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017700/b0177007.png" /> contain at most 9 prime factors.
+
{{TEX|done}}
 +
 
 +
A [[Sieve method|sieve method]] in elementary number theory, proposed by V. Brun [[#References|[1]]]; it is an extension of the sieve of Eratosthenes (cf. [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). The method of Brun's sieve may be described as follows. Out of a sequence of natural numbers $a_n\leq x$ the numbers with small prime divisors are eliminated ( "sieved out" ) leaving behind prime and almost-prime numbers (cf. [[Almost-prime number|Almost-prime number]]) with only large prime divisors. Let $P(x)$ be the amount of these numbers. It can be shown that $P(x)$ is included between two sums with a relatively-small number of summands, which may be estimated from above and from below. Thus, it is possible to evaluate from above the number of [[Twins|twins]] in a given interval. Brun's sieve is employed in additive number theory. Brun used his sieve to prove that all large even numbers $N$ can be represented in the form $N=P_1+P_2$, where $P_1$ and $P_2$ contain at most 9 prime factors.
  
 
====References====
 
====References====

Latest revision as of 07:18, 11 December 2012


A sieve method in elementary number theory, proposed by V. Brun [1]; it is an extension of the sieve of Eratosthenes (cf. Eratosthenes, sieve of). The method of Brun's sieve may be described as follows. Out of a sequence of natural numbers $a_n\leq x$ the numbers with small prime divisors are eliminated ( "sieved out" ) leaving behind prime and almost-prime numbers (cf. Almost-prime number) with only large prime divisors. Let $P(x)$ be the amount of these numbers. It can be shown that $P(x)$ is included between two sums with a relatively-small number of summands, which may be estimated from above and from below. Thus, it is possible to evaluate from above the number of twins in a given interval. Brun's sieve is employed in additive number theory. Brun used his sieve to prove that all large even numbers $N$ can be represented in the form $N=P_1+P_2$, where $P_1$ and $P_2$ contain at most 9 prime factors.

References

[1] V. Brun, "Le crible d'Eratosthène et le théorème de Goldbach" C.R. Acad. Sci. Paris Sér. I Math. , 168 : 11 (1919) pp. 544–546
[2] A.O. Gel'fond, Yu.V. Linnik, "Elementary methods in the analytic theory of numbers" , M.I.T. (1966) (Translated from Russian)
[3] E. Trost, "Primzahlen" , Birkhäuser (1953)


Comments

References

[a1] H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974)
How to Cite This Entry:
Brun sieve. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Brun_sieve&oldid=29166
This article was adapted from an original article by N.I. Klimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article