The task is to determine a bound for the number of distinct prime divisors. The proof can be found here:

The smallest number with $k$ distinct prime divisors is the $k^\text{th}$ primorial. So the most distinct prime divisors for any number up to $x$ will be the the number of divisors of the largest primorial less than or equal to $x$. We know from the primorial asymptotic that this is $\ln(x)\#$. And we know from the Prime Number Theorem that the number of primes less than $\ln(x)$ is $\ln(x)/\ln(\ln(x))$.

Since the upper bound is given by the primorial, we have $\omega(x)\le\omega(x\#)$. By definition, $\omega(x\#)=\pi(x)$. Finally, by the prime number theorem, $\pi(x)\sim x/\ln(x)$. I don't understand how one can conclude that the bound is given by $\ln(x)/\ln(\ln(x))$.


Not $\omega(x)\le\omega(x\#)$, that's an extremely loose bound. The text talks about the largest primorial $\le x$, which isn't $x\#$, but apparently is $\ln(x)\#$. Then $\omega(x)\le\omega(\ln(x)\#)=\pi(\ln(x))\sim \ln(x)/\ln(\ln(x))$.

  • $\begingroup$ Thanks! Do you know why we can use $\ln(x)\#$ instead of $\ln(x\#)$ in the primorial asymptotic? $\endgroup$ – Anonymous - a group Apr 9 '16 at 11:48
  • $\begingroup$ @Anonymous-agroup: $\ln(x\#)\sim x$ shows that taking the primorial is roughly the inverse of taking the natural logarithm; it doesn't matter whether you first apply the logarithm and then the inverse or vice versa. That's not a rigorous argument, though, since exponentiating an asymptotic equivalence doesn't necessarily result in an asymptotic equivalence. $\endgroup$ – joriki Apr 9 '16 at 12:10
  • $\begingroup$ $x \# = \prod_{p \le x} p$ and that's the prime number theorem that $\sum_{p \le x} \ln p \sim x$ (the PNT is $\pi(x) = \sum_{p \le x} 1 \sim \frac{x}{\ln x}$ but you prove $\sum_{p \le x} \ln p \sim x$ before) $\endgroup$ – reuns Apr 9 '16 at 12:53
  • $\begingroup$ @user1952009: That shows that $\ln(x\#)\sim x$; the question was why we can use $\ln(x)\#$ instead. $\endgroup$ – joriki Apr 9 '16 at 13:02
  • $\begingroup$ yes but this is quite absurd and un-necessary. I just wrote what is necessary to know for solving the exercice $\endgroup$ – reuns Apr 9 '16 at 13:04

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.