I've been working on this homework exercise for quite some time now and I just won't succeed. Any help would be appreciated.
Let $\omega(n)$ be the number of distinct prime divisors of $n$. I need to prove that $\omega(n) = O\left(\frac{\log(n)}{\log\log(n)}\right)$ as $x\to\infty$. There is a hint which says to first prove $\omega(n)!\le n$ (which was easy) . Furthermore, I may use $\omega(n)!\ge \exp(\omega(n)\log(\omega(n))-\omega(n))$.
From these hints it follows that $\omega(n)\log(\omega(n))-\omega(n) \le \log(n)$ and thus $\omega(n) \le \log(n)/(\log(\omega(n))-1)$, but then I get stuck.
Alternatively, $\omega(n)\log(\omega(n)) \le \log(n) + \omega(n) \le 2\log(n)$ and I get stuck again.
I've found a proof which I understand but it does not use any of the hints. Since I have been giving this some time now, I would really like to know how to do it in the way suggested by the exercise.
Thanks in advance!
Answer
Once you have the inequality $\omega(n) \log \omega(n) \leq 2\log n$ you're basically there. Now assume for contradiction that for all large enough $n$ we have $\omega(n) > C \frac{\log n}{\log \log n}$. Here $C$ is some large constant, though actually $C>2$ suffices.
No comments:
Post a Comment