# How is $O(\log x/\log \log x)$ an upper bound on the number of distinct prime factors of $x$?

This is Problem 10.22 in The Nature Of Computation.

Show that any integer $$x$$ has at most $$O(\log x/\log \log x)$$ distinct prime factors. Hint: if we list the primes in increasing order, the $$i$$th prime is at least $$i$$.

The solution manual argues:

Since the $$i$$th prime is at least $$i$$, if $$x$$ has $$d$$ distinct factors then $$x \geq d!$$. Stirling's approximation gives $$d! \geq d^d e^{-d}$$, so if we pessimistically assume that $$x = d!$$ we have $$\log x = \Theta(d\log d)$$ and $$\log \log x = \Theta(\log d)$$. Then $$d = \Theta\bigg(\frac{\log x}{\log d}\bigg) = \Theta\bigg(\frac{\log x}{\log \log x}\bigg)\,,$$ Replacing $$\Theta$$ with $$O$$ gives an upper bound that holds when $$x \geq d!$$.

This deduction doesn't appear fully kosher to me. Since we're interested in an upper bound for $$d$$ we need the lower bound $$\log d \geq \log \log x$$ for the central statement to hold. But we don't have such a lower bound. We pessimistically assumed that $$x = d!$$. In other words, $$x \geq d!$$. We can turn this into $$\log \log x \geq \alpha \log d$$ for some constant $$\alpha$$. But this inequality is pointing in the wrong direction.

I agree that there is a slight problem, but I don't see it at exactly the same place as you. It may also be irritating that it sets $$x=d!$$ 'pessimisticly', when that is really not necessary and $$d!$$ can be used at all times until the very end.

The problem is IMO the moment the proof goes from an inequality $$d! \ge d^de^{-d}$$ to a $$\Theta$$-statement, that requires inequalities in both directions. To put it bluntly, clearly, $$d! \ge 1$$, but obviously not $$\log (d!) = \Theta(0)$$.

Of course, the Stirling approximation provides the necessary accurancy that the inequality lacks:

$$d! \sim \sqrt{2\pi d}\space d^de^{-d}$$

which means (much more but also) there are $$c_1,c_2 > 0$$ with $$c_1\sqrt{2\pi d}\space d^de^{-d} \le d! \le c_2\sqrt{2\pi d}\space d^de^{-d},$$

which further imples

$$\log (c_1) + \frac12\log (2\pi) + \frac12\log (d) + d\log d-d \le \log d! \le \log (c_2) + \frac12\log (2\pi) + \frac12\log (d) + d\log d-d,$$

and on both sides the term $$d\log d$$-term dominates, the remaining terms are just $$o(d\log d)$$, so we get (as stated in the proof, but not really validated):

$$\log (d!) = \Theta (d\log d).$$

From that follows in the same way the also used:

$$\log \log (d!) = \Theta (\log d),$$

and we finally get

$$d=\Theta \left({\log (d!) \over \log\log (d!)}\right).$$

Note that this is a statement only about $$d$$ and $$d!$$, nothing about the original problem is used here. That statement implies there is a $$c>0$$ with

$$d \le c{\log (d!) \over \log\log (d!)}$$.

Now, to tackle the original problem, all that is now needed is to see that

$$d \le c{\log (x) \over \log\log (x)}$$

(with the exact same $$c$$ as before) is to simply note that $$f(x)={\log (x) \over \log\log x}$$ is monotincally increasing (for $$x \ge e^e$$), because $$g(y)={y \over \log y}$$ is monotonically increasing for $$y \ge e$$ and remember that $$x \ge d!$$.