Approximating the number of integers free of large prime factors (1997)

Define <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Psi left-parenthesis x comma y right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Ψ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\Psi (x,y)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to be the number of positive integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-equal-to x"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>x</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\le x</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has no prime divisor larger than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="y"> <mml:semantics> <mml:mi>y</mml:mi> <mml:annotation encoding="application/x-tex">y</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We present a simple algorithm that approximates <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Psi left-parenthesis x comma y right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Ψ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\Psi (x,y)</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 y left-brace StartFraction log log x Over log y EndFraction plus StartFraction 1 Over log log y EndFraction right-brace right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>y</mml:mi> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>x</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>y</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>y</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(y\{\frac {\log \log x}{\log y} + \frac 1{\log \log y}\})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Psi left-parenthesis x comma y right-parenthesis almost-equals x rho left-parenthesis log x slash log y right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Ψ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≈</mml:mo> <mml:mi>x</mml:mi> <mml:mi>ρ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>y</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\Psi (x,y)\approx x\rho (\log x/\log y)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="rho left-parenthesis u right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>ρ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>u</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\rho (u)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is Dickman’s function.