This question already has an answer here:

At the top of the second page of this paper by Ramanujan, he states that "by purely elementary reasoning", where $f(n)$ is the number of distinct prime factors of $n$, we have that for all $\varepsilon > 0$, $$ f(n) < (1+\varepsilon)\frac{\log n}{\log \log n} $$ for all sufficiently large $n$, and $$ f(n) > (1-\varepsilon) \frac{\log n}{\log \log n} $$ for infinitely many values of $n$, so that the maximum order of $f(n)$ is $$ \frac{\log n}{\log \log n}. $$ What's the simple reason for this he had in mind?


Edit: notation clarified per Thomas Andrews' comment.


marked as duplicate by Dietrich Burde, Daniel Fischer Jul 6 '17 at 14:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ In older mathematical writing, "elementary" didn't necessarily mean "simple" - it just meant that the result in question could be proven with real-analytic techniques (as opposed to complex-analytic). $\endgroup$ – MathematicsStudent1122 Jul 6 '17 at 13:44
  • $\begingroup$ I'm not sure that $\sim$ is the right symbol, at least as usually used. But it might be an upper bound. $\endgroup$ – Thomas Andrews Jul 6 '17 at 13:45
  • $\begingroup$ my first thought is that the en.wikipedia.org/wiki/Prime_number_theorem says that there are roughly ${N}\over{log(n)}$ primes up to N and maybe taking the log of this results in the formula ? $\endgroup$ – user451844 Jul 6 '17 at 14:02
  • $\begingroup$ @MathematicsStudent1122 Interesting, thanks. $\endgroup$ – Derek Allums Jul 6 '17 at 14:04
  • $\begingroup$ @ThomasAndrews I think you're right, and have edited the question. $\endgroup$ – Derek Allums Jul 6 '17 at 14:04

$\omega(n)$ is maximized by primorials, and by the prime number theorem $p_k\sim k\log k$ $$ \prod_{k=1}^{n}p_k = \exp\sum_{k=1}^{n}\log p_k \stackrel{\text{Stirling}}{\sim}\exp\left(n\log n + n\log\log n\right)$$ so $\omega(n)<(1+\varepsilon)\frac{\log n}{\log\log n}$ follows by considering primorials. On the other hand the square-free numbers have a positive density ($\frac{6}{\pi^2}$) in $\mathbb{N}$ and loosely speaking the previous bound does not change by much if a primorial is replaced by a square-free number with a lot of small prime factors. The bound $\omega(n)>(1-\varepsilon)\frac{\log n}{\log\log n}$ can so be achieved by considering square-free numbers.


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