Difference between revisions of "MeisselLehmer method"
(3 intermediate revisions by 3 users not shown)  
(No difference)

Latest revision as of 06:39, 29 February 2012
The MeisselLehmer 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 aalmost 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,a1)  \pi(x/a, a)[/math] (2)
which reflects the basic fact that the a1almost primes are the union of the aalmost primes, and the a1almost 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.