http://michaelnielsen.org/polymath1/api.php?action=feedcontributions&user=Piternoize&feedformat=atom Polymath1Wiki - User contributions [en] 2019-10-17T11:39:05Z User contributions MediaWiki 1.23.5 http://michaelnielsen.org/polymath1/index.php?title=Meissel-Lehmer_method Meissel-Lehmer method 2012-02-22T10:50:45Z <p>Piternoize: </p> <hr /> <div>The '''Meissel-Lehmer method''' is a combinatorial method for computing &lt;math&gt;\pi(x)&lt;/math&gt; in time/space &lt;math&gt;x^{2/3+o(1)}&lt;/math&gt;. It is analysed at [http://www.dtc.umn.edu/~odlyzko/doc/arch/meissel.lehmer.pdf LMO???]<br /> <br /> Define an &lt;math&gt;x^{1/3}&lt;/math&gt;-''almost prime'' to be an integer less than x not divisible by any prime less than &lt;math&gt;x^{1/3}&lt;/math&gt;; such a number is either a prime, or a product of two primes which are between &lt;math&gt;x^{1/3}&lt;/math&gt; and &lt;math&gt;x^{2/3}&lt;/math&gt;. Each number of the latter form can be written in two ways as the product of a prime p between &lt;math&gt;x^{1/3}&lt;/math&gt; and &lt;math&gt;x^{2/3}&lt;/math&gt;, and a prime between &lt;math&gt;x^{1/3}&lt;/math&gt; and &lt;math&gt;x/p&lt;/math&gt;, except for the squares of primes between &lt;math&gt;x^{1/3}&lt;/math&gt; and &lt;math&gt;x^{1/2}&lt;/math&gt; which only have one such representation. The number &lt;math&gt;\pi(x,x^{1/3})&lt;/math&gt; of almost primes less than x is thus<br /> <br /> :&lt;math&gt; \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}))&lt;/math&gt; (1)<br /> <br /> (ignoring some floor and ceiling functions).<br /> <br /> Using the sieve of Erathosthenes, one can compute &lt;math&gt;\pi(y)&lt;/math&gt; for all &lt;math&gt;y \leq x^{2/3}&lt;/math&gt; in time/space &lt;math&gt;x^{2/3+o(1)}&lt;/math&gt;, so every expression in (1) is computable in this time except for &lt;math&gt;\pi(x)&lt;/math&gt;. So it will suffice to compute the number of &lt;math&gt;x^{1/3}&lt;/math&gt;-almost primes less than x in time &lt;math&gt;x^{2/3+o(1)}&lt;/math&gt;.<br /> <br /> If we let &lt;math&gt;\pi(x,a)&lt;/math&gt; 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<br /> <br /> :&lt;math&gt;\pi(x,a) = \pi(x,a-1) - \pi(x/a, a)&lt;/math&gt; (2)<br /> <br /> 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 &lt;math&gt;x^{1/3}&lt;/math&gt; by the sieve of Eratosthenes, we can store &lt;math&gt;\pi(y,a)&lt;/math&gt; for all &lt;math&gt;a, y \leq x^{1/3}&lt;/math&gt;, to be retrievable in O(1) time. Meanwhile, by recursively expanding out (2) until the x parameter dips below &lt;math&gt;x^{1/3}&lt;/math&gt;, one can express &lt;math&gt;\pi(x,x^{1/3})&lt;/math&gt; as an alternating sum of various &lt;math&gt;\pi(y,b)&lt;/math&gt; with &lt;math&gt;y,b \leq x^{1/3}&lt;/math&gt;, with each &lt;math&gt;\pi(y,b)&lt;/math&gt; occurring at most once; summing using the stored values then gives &lt;math&gt;\pi(x,x^{1/3})&lt;/math&gt; as required.<br /> [http://www.resumesplanet.com resume help] [http://www.assignmentexpert.com/custom-assignment.html mathematics assignment custom writing]</div> Piternoize