- #1

- 13

- 0

## Homework Statement

Let [itex]f(n)[/itex] denote the number of unique prime factors of some positive integer [itex]n > 1[/itex]. Prove that [itex]f(n) \in \mathcal{O}\left(\dfrac{\log n}{\log \log n}\right)[/itex]

## Homework Equations

## The Attempt at a Solution

Since every prime number except 2 is prime, an upper bound on the number of prime factors of any [itex]n[/itex] would be [itex]k[/itex] such that

[tex]\displaystyle{\dfrac{n}{\prod_{i=1}^{k}\left(2i-1\right)}=1}[/tex]

[tex]\ln n=\sum_{i=1}^{k}\ln\left(2i-1\right)[/tex]

Using AM-GM inequality,

[tex]\sum_{i=1}^{k}\ln\left(2i-1\right)\geq k\sqrt[k]{\prod_{i=1}^{k}\left(2i-1\right)}=k\sqrt[k]{n}[/tex]

The best I can arrive at is:

[tex]\ln\ln n\geq\ln k+\dfrac{1}{k}\ln n[/tex]

which is ugly. I've also tried attacking this with

[tex]\dfrac{\sqrt{n}}{\prod_{i=1}^{k}\left(2i-1\right)}=1[/tex]

instead, but this makes my inequality uglier.

What should I do? Thanks!