Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

Abstract

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>π<!-- π --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the number of primes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="less-than-or-equal-to x"> <mml:semantics> <mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>x</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\le x</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Our aim in this paper is to present some refinements of a combinatorial method for computing single values of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>π<!-- π --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>π<!-- π --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartFraction x Superscript 2 slash 3 Baseline Over log squared x EndFraction right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mfrac> <mml:msup> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:msup> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\frac {x^{2/3}} {\log ^2x})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> time and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis x Superscript 1 slash 3 Baseline log cubed x log log x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>log</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(x^{1/3}\log ^3x\log \log x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> space. The algorithm has been implemented and used to compute <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis 10 Superscript 18 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>π<!-- π --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>18</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (10^{18})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.

Locations

• Mathematics of Computation - View - PDF
• HAL (Le Centre pour la Communication Scientifique Directe) - View