0
$\begingroup$

I am trying to approximate the number of integers less than $x$ that have no prime factors less than $B$. Is such an approximation known? If so, how good is it?

Note that this should not be confused with approximating $x - \Psi(x, B)$, since that would approximate the numbers less than $x$ that have at least one prime factor greater than or equal to $B$.

$\endgroup$
  • $\begingroup$ Perhaps you are thinking about smooth numbers, in which case, see: en.wikipedia.org/wiki/Smooth_number $\endgroup$ – BlackAdder Feb 17 '14 at 1:54
  • $\begingroup$ See my note: it is not so simple as subtracting from x the number of B-smooth numbers less than x. $\endgroup$ – Gnosis_X Feb 18 '14 at 4:48
1
$\begingroup$

Hint: How many primes are there in between B and X ? How many of their products are less then X ? For the first question, see prime-counting function $\pi(n)\simeq\dfrac n{\ln n}$ . For the second, $p_k^2\in[B^2,x]$ would be a necessary, though insufficient, first condition.

$\endgroup$
  • $\begingroup$ Did you mean to put $=$ there? $\endgroup$ – Matthew Conroy Feb 17 '14 at 2:06
  • $\begingroup$ No. I meant that, apart from the actual primes in between B and X, the smallest composites are of the form $p_jp_k$, with both $p_j$ and $p_k$ in between B and X. But that first prime $\ge B$ also has to be $\le\sqrt x$ in order for such composites to even exist... $\endgroup$ – Lucian Feb 17 '14 at 2:28
  • $\begingroup$ I meant the $\pi(n)=n/\ln n$ statement. $\endgroup$ – Matthew Conroy Feb 17 '14 at 2:37
  • $\begingroup$ Oh! Sorry. :-) I've fixed it now. $\endgroup$ – Lucian Feb 17 '14 at 2:42
  • $\begingroup$ I am not sure how to fully and correctly express this in mathematical notation, but is the solution: $(\pi(x)-\pi(B)) + (\pi(x^{\frac{1}{2}})-\pi(B))^2 + (\pi(x^{\frac{1}{3}})-\pi(B))^3 + ...$ until the first term in which $\pi(x^{\frac{1}{i}})-\pi(B)$ is negative? $\endgroup$ – Gnosis_X Feb 18 '14 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.