Meissel-Lehmer method: Difference between revisions
No edit summary |
No edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 14: | Line 14: | ||
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. | 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. | ||
Latest revision as of 22:39, 28 February 2012
The Meissel-Lehmer method is a combinatorial method for computing [math]\displaystyle{ \pi(x) }[/math] in time/space [math]\displaystyle{ x^{2/3+o(1)} }[/math]. It is analysed at LMO???
Define an [math]\displaystyle{ x^{1/3} }[/math]-almost prime to be an integer less than x not divisible by any prime less than [math]\displaystyle{ x^{1/3} }[/math]; such a number is either a prime, or a product of two primes which are between [math]\displaystyle{ x^{1/3} }[/math] and [math]\displaystyle{ 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]\displaystyle{ x^{1/3} }[/math] and [math]\displaystyle{ x^{2/3} }[/math], and a prime between [math]\displaystyle{ x^{1/3} }[/math] and [math]\displaystyle{ x/p }[/math], except for the squares of primes between [math]\displaystyle{ x^{1/3} }[/math] and [math]\displaystyle{ x^{1/2} }[/math] which only have one such representation. The number [math]\displaystyle{ \pi(x,x^{1/3}) }[/math] of almost primes less than x is thus
- [math]\displaystyle{ \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]\displaystyle{ \pi(y) }[/math] for all [math]\displaystyle{ y \leq x^{2/3} }[/math] in time/space [math]\displaystyle{ x^{2/3+o(1)} }[/math], so every expression in (1) is computable in this time except for [math]\displaystyle{ \pi(x) }[/math]. So it will suffice to compute the number of [math]\displaystyle{ x^{1/3} }[/math]-almost primes less than x in time [math]\displaystyle{ x^{2/3+o(1)} }[/math].
If we let [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ x^{1/3} }[/math] by the sieve of Eratosthenes, we can store [math]\displaystyle{ \pi(y,a) }[/math] for all [math]\displaystyle{ 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]\displaystyle{ x^{1/3} }[/math], one can express [math]\displaystyle{ \pi(x,x^{1/3}) }[/math] as an alternating sum of various [math]\displaystyle{ \pi(y,b) }[/math] with [math]\displaystyle{ y,b \leq x^{1/3} }[/math], with each [math]\displaystyle{ \pi(y,b) }[/math] occurring at most once; summing using the stored values then gives [math]\displaystyle{ \pi(x,x^{1/3}) }[/math] as required.
