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}$$

  • 2
    $\begingroup$ This seems to be a question about pure Mathematics. What's the computational aspect that you're looking for help with? $\endgroup$ – David Richerby Apr 4 '18 at 15:34
  • $\begingroup$ 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? $\endgroup$ – billz Apr 4 '18 at 15:41
  • $\begingroup$ 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. :-) $\endgroup$ – David Richerby Apr 4 '18 at 15:47
  • $\begingroup$ Agree with Dave. This should be migrated to Mathematics. $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – billz Apr 4 '18 at 15:54
  • $\begingroup$ I understand now, just had to reread the MathWorld link...thanks again. $\endgroup$ – billz Apr 4 '18 at 15:58
  • $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus Apr 4 '18 at 15:58
  • $\begingroup$ @billz: Instead of answering "what is the maximum number of distinct prime factors of n", you just reverse the question "which is the smallest integer with k or more distinct prime factors". $\endgroup$ – gnasher729 Apr 4 '18 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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