Bound number of integers not exceeding x composed of primes $p_1, p_2, ..., p_k$

93 Views Asked by At

I am trying to bound the number of integers less than $x$ composed of primes $p_1,p_2,...,p_k$ only. Is there any way to do so without breaking that number into subsets of the form $$ set\space of\space all\space integers\space less\space that\space x\space composed\space of\space primes\space p_1,..., p_k\space such\space that\space members\space of\space this\space subset\space have\space less\space than\space (more\space than\space)K\space distinct\space prime\space factors$$

Thanks!

2

There are 2 best solutions below

0
On

I'm not sure if this is what you're looking for, but there's a really nice upper bound which was used by Erdös in his proof that the series of reciprocal primes is divergent. (See, for instance, the Wikipedia article about this.)

The argument is as follows: Let

\begin{align*} M = \lbrace 1 \leqslant s \leqslant x \mid \text{$s$ is not divisible by a prime greater than or equal to $p_k$} \rbrace. \end{align*} Now, any integer in $M$ (or any integer in general, for that matter) can be written uniquely as $rm^2$ where $r,m \in \mathbb{Z}$, and $r$ is square-free. Since there are exactly $2^k$ choices for $r$, and since $m^2 \leqslant x$, and so $m \leqslant \sqrt{x}$, the number of different $rm^2$ belonging to $M$ is at most $2^k \sqrt{x}$;

\begin{align*} |M| \leqslant 2^k \sqrt{x}. \end{align*}

0
On

In this answer I justify an approximation of $\frac {(\log x)^k}{k!\log 2 \cdot \log 3 \cdot \ldots \log p_k}$