Difference between revisions of "Meissel-Lehmer method"

From Polymath1Wiki
Jump to: navigation, search
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
The '''Meissel-Lehmer method''' is a combinatorial method for computing <math>\pi(x)</math> in time/space <math>x^{2/3+o(1)}</math>.  It is analysed at [http://www.dtc.umn.edu/~odlyzko/doc/arch/meissel.lehmer.pdf LMO???]
 
The '''Meissel-Lehmer method''' is a combinatorial method for computing <math>\pi(x)</math> in time/space <math>x^{2/3+o(1)}</math>.  It is analysed at [http://www.dtc.umn.edu/~odlyzko/doc/arch/meissel.lehmer.pdf LMO???]
  
Define an <math>x^{1/3}</math>-''almost prime'' to be an integer less than x not divisible by any prime less than <math>x^{1/3}</math>; such a number is either a prime, or a product of two primes which are between <math>x^{1/3}</math> and <math>x^{2/3}</math>.  Each number of the latter form can be written in two ways as the product of a prime p between <math>x^{1/3}</math> and <math>x^{2/3}</math>, and a prime between <math>x^{1/3}</math> and <math>x/p</math>, except for the squares of primes between <math>x^{1/3}</math> and <math>x^{1/2}</math> which only have one such representation.  The number of almost primes less than x is thus
+
Define an <math>x^{1/3}</math>-''almost prime'' to be an integer less than x not divisible by any prime less than <math>x^{1/3}</math>; such a number is either a prime, or a product of two primes which are between <math>x^{1/3}</math> and <math>x^{2/3}</math>.  Each number of the latter form can be written in two ways as the product of a prime p between <math>x^{1/3}</math> and <math>x^{2/3}</math>, and a prime between <math>x^{1/3}</math> and <math>x/p</math>, except for the squares of primes between <math>x^{1/3}</math> and <math>x^{1/2}</math> which only have one such representation.  The number <math>\pi(x,x^{1/3})</math> of almost primes less than x is thus
  
 
:<math> \pi(x) - \pi(x^{1/3}) +  \frac{1}{2} \sum_{x^{1/3} \leq p \leq x^{2/3}} [\pi( x/p ) - \pi(x^{1/3})] + \frac{1}{2} (\pi(x^{1/2})-\pi(x^{1/3}))</math> (1)
 
:<math> \pi(x) - \pi(x^{1/3}) +  \frac{1}{2} \sum_{x^{1/3} \leq p \leq x^{2/3}} [\pi( x/p ) - \pi(x^{1/3})] + \frac{1}{2} (\pi(x^{1/2})-\pi(x^{1/3}))</math> (1)
Line 11: Line 11:
 
If we let <math>\pi(x,a)</math> denote the number of a-almost primes less than x (i.e. the number of integers less than x not divisible by any integer between 2 and a), we have the recurrence
 
If we let <math>\pi(x,a)</math> denote the number of a-almost primes less than x (i.e. the number of integers less than x not divisible by any integer between 2 and a), we have the recurrence
  
:<math>\pi(x,a) = \pi(x,a-1) - \pi(x/a, a)</math>
+
:<math>\pi(x,a) = \pi(x,a-1) - \pi(x/a, a)</math> (2)
  
which reflects the basic fact that the a-1-almost primes are the union of the a-almost primes, and the a-1-almost primes multiplied by a.  On the other hand, by factoring all the numbers up to <math>x^{2/3}</math> by the sieve of Eratosthenes, we can store <math>\pi(y,a)</math> for all <math>a, y \leq x^{2/3}</math>, to be retrievable in O(1) time.  One can then show by induction that <math>\pi(y,a)</math> is computable for larger a,y in time <math> O_\varepsilon( (ay)^{1+\varepsilon} / x^{2/3} )</math> for any <math>\varepsilon > 0</math>, which gives the <math>x^{2/3+o(1)}</math> algorithm.
+
which reflects the basic fact that the a-1-almost primes are the union of the a-almost primes, and the a-1-almost primes multiplied by a.  On the other hand, by factoring all the numbers up to <math>x^{1/3}</math> by the sieve of Eratosthenes, we can store <math>\pi(y,a)</math> for all <math>a, y \leq x^{1/3}</math>, to be retrievable in O(1) time.  Meanwhile, by recursively expanding out (2) until the x parameter dips below <math>x^{1/3}</math>, one can express <math>\pi(x,x^{1/3})</math> as an alternating sum of various <math>\pi(y,b)</math> with <math>y,b \leq x^{1/3}</math>, with each <math>\pi(y,b)</math> occurring at most once; summing using the stored values then gives <math>\pi(x,x^{1/3})</math> as required.
 
+
[ Note: the above paragraph needs to be checked ]
+

Latest revision as of 23:39, 28 February 2012

The Meissel-Lehmer method is a combinatorial method for computing [math]\pi(x)[/math] in time/space [math]x^{2/3+o(1)}[/math]. It is analysed at LMO???

Define an [math]x^{1/3}[/math]-almost prime to be an integer less than x not divisible by any prime less than [math]x^{1/3}[/math]; such a number is either a prime, or a product of two primes which are between [math]x^{1/3}[/math] and [math]x^{2/3}[/math]. Each number of the latter form can be written in two ways as the product of a prime p between [math]x^{1/3}[/math] and [math]x^{2/3}[/math], and a prime between [math]x^{1/3}[/math] and [math]x/p[/math], except for the squares of primes between [math]x^{1/3}[/math] and [math]x^{1/2}[/math] which only have one such representation. The number [math]\pi(x,x^{1/3})[/math] of almost primes less than x is thus

[math] \pi(x) - \pi(x^{1/3}) + \frac{1}{2} \sum_{x^{1/3} \leq p \leq x^{2/3}} [\pi( x/p ) - \pi(x^{1/3})] + \frac{1}{2} (\pi(x^{1/2})-\pi(x^{1/3}))[/math] (1)

(ignoring some floor and ceiling functions).

Using the sieve of Erathosthenes, one can compute [math]\pi(y)[/math] for all [math]y \leq x^{2/3}[/math] in time/space [math]x^{2/3+o(1)}[/math], so every expression in (1) is computable in this time except for [math]\pi(x)[/math]. So it will suffice to compute the number of [math]x^{1/3}[/math]-almost primes less than x in time [math]x^{2/3+o(1)}[/math].

If we let [math]\pi(x,a)[/math] denote the number of a-almost primes less than x (i.e. the number of integers less than x not divisible by any integer between 2 and a), we have the recurrence

[math]\pi(x,a) = \pi(x,a-1) - \pi(x/a, a)[/math] (2)

which reflects the basic fact that the a-1-almost primes are the union of the a-almost primes, and the a-1-almost primes multiplied by a. On the other hand, by factoring all the numbers up to [math]x^{1/3}[/math] by the sieve of Eratosthenes, we can store [math]\pi(y,a)[/math] for all [math]a, y \leq x^{1/3}[/math], to be retrievable in O(1) time. Meanwhile, by recursively expanding out (2) until the x parameter dips below [math]x^{1/3}[/math], one can express [math]\pi(x,x^{1/3})[/math] as an alternating sum of various [math]\pi(y,b)[/math] with [math]y,b \leq x^{1/3}[/math], with each [math]\pi(y,b)[/math] occurring at most once; summing using the stored values then gives [math]\pi(x,x^{1/3})[/math] as required.