I am trying to prove a relatively simple bound for the problem below. I want someone to check if my solution is good :)

For a $P=\{ p_1,p_2,...,p_k \}$ a set of prime factors, we define as $N_P= \{ n\in \mathbb{N}: p|n \Rightarrow p\in P \}$. We also define as $N_P(x)= \# \{n\in N_P : n \leq x \}$.

I want to prove that exist a constant $C$ and a $x_0$, which depend on $P$, such that: $$ N_P(x) \leq C (\log x)^k \; \text{for $x \geq x_0$} $$

My attempt:

My first idea was to use somehow use the Prime Number Theorem (PMT): $\pi(x) \sim x/\log x $, for a sufficiently large $x$. But since the $\log$ is on the denominator, I think this is hopeless.

So I made this argument: Let $n\in N_P$, then $n$ has prime factorization that contains only primes from the set $P$.

Thus $n=p_1^{n_1}p_2^{n_2}...p_k^{n_k}$. For $n \leq x$, we must have that: $ p_i^{n_i} \leq x \Rightarrow n_i \leq \frac{\log x}{\log p_i} $ for $\forall i$.

Thus for $x\geq p_k$ $$N_p \leq \frac{\log x}{\log p_1} \frac{\log x}{\log p_2} ... \frac{\log x}{\log p_k} = \frac{1}{\log p_1 \log p_2 ... \log p_k} (\log x)^k = C (\log x)^k $$ for $x\geq x_0=p_k $.

What do you think? Thanks in advance for your time!

  • 1
    $\begingroup$ This... looks reasonable to me. I'm not 100% certain; others may have quibbles. $\endgroup$ Commented Jan 20, 2023 at 0:32
  • $\begingroup$ "a set of prime factors"? factors of what? "a set of prime numbers" $\endgroup$
    – jjagmath
    Commented Jan 20, 2023 at 0:32
  • $\begingroup$ Why do you think you have to consider $x \ge p_k$? $\endgroup$
    – jjagmath
    Commented Jan 20, 2023 at 0:37
  • $\begingroup$ Write $n=\prod_j p_j^{e_j}$, if $n\le x$ then $e_j \le \log_{p_j}(x)$ so there are at most $f(x)=\prod_j (1+\log_{p_j}(x))$ choices for the $e_j$ ie. at most $f(x)$ integers $\le x$ whose all prime factors are in the $p_j$. $\endgroup$
    – reuns
    Commented Jan 20, 2023 at 0:38
  • $\begingroup$ A detail about MathJax: Don't write log\; x ($log\; x$) write \log x ($\log x$). $\endgroup$
    – jjagmath
    Commented Jan 20, 2023 at 0:47

1 Answer 1


There's a little problem in your proof:

After you get $n_i \le \frac{\log x}{\log p_i}$ you need to consider that $n_i$ can take $\left\lfloor \frac{\log x}{\log p_i}\right\rfloor \color{red}{+1}$ values, because $n_i$ can be $0$.

  • $\begingroup$ Hardy discussed the case $k=2$ when discussing a result of Ramanujan. I think the general result was done by Landau. $\endgroup$ Commented Jan 20, 2023 at 1:23
  • $\begingroup$ @martycohen This comment should be in the question section, is not about my answer. $\endgroup$
    – jjagmath
    Commented Jan 20, 2023 at 1:34
  • $\begingroup$ Yes I totally missed that, thank you. $\endgroup$ Commented Jan 20, 2023 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .