# Show a sequence of distinct Primes number is O(log n)

Suppose I have a sequence:

$$n = \prod_{i=1}^{r(n)} p_i^{d_i}$$

for some primes $p_1 < p_2 < \dots < p_{r(n)}$, and each $d_i \geq 1$ an integer. The function $r(n)$ denotes the number of distinct primes divisor of $n$.

I'm trying to show $r(n) = O(\log n)$.

What I have tried: I think I can establish an upper bound on $\prod_{i=1}^{r(n)} p_i^{d_i}$ to show its asymptotic bound.

To simplify and without loss of generality, let $d_i = 1$. Then,

$$n = \prod_{i=1}^{r(n)} p_i$$ $$\log n = \log (\prod_{i=1}^{r(n)} p_i)$$ $$\log n \geq \Sigma_{i=1}^{r(n)} \log p_i$$

Then not sure where to go from here.

I think I want to show something like:

$$\log n \geq \frac{r(n) + 1}{2}$$

• This seems to be a question about pure Mathematics. What's the computational aspect that you're looking for help with? – David Richerby Apr 4 '18 at 15:34
• I wasn't sure if I should post to computer science or to mathematics. I was inclined to post here since it deals with asymptotic bounds. Should I move it? – billz Apr 4 '18 at 15:41
• I think so, but you might want to wait to see if anyone else has an opinion. Aaaaand then you got an answer while I was writing my comment, so I guess you may as well leave it. :-) – David Richerby Apr 4 '18 at 15:47
• Agree with Dave. This should be migrated to Mathematics. – Yuval Filmus Apr 4 '18 at 15:49

Since each of the prime numbers is at least 2, we have $$n \geq \prod_{i=1}^{r(n)} p_i \geq \prod_{i=1}^{r(n)} 2 = 2^{r(n)},$$ from which it follows that $r(n) \leq \log_2 n$.
In fact, since the prime numbers are generally larger than 2, we can obtain a better bound, namely $$r(n) \lesssim \frac{\log n}{\log \log n}.$$ See for example MathWorld, which states the number of distinct prime factors in a primorial.
• Thank you. I understand your answer of $r(n) \leq \log_2 n$ which is helpful. Could you expand a little bit on the second part, obtaining a better bound? I checked MathWorld (which I did stumble across before) – billz Apr 4 '18 at 15:54
• We can improve the bound given in the first part using $n \geq q_1 q_2 \dots q_{r(n)}$, where $q_1,q_2,\ldots$ is the sequence of primes. The term on the right-hand side is a primorial. It remains to estimate the rate of growth of primorial. MathWorld states that primorials satisfy $r(n) \sim \frac{\log n}{\log \log n}$. – Yuval Filmus Apr 4 '18 at 15:58